;;;  tiles.scm    Dave Reed    9/04/08
;;;  NOTE: this is an UGLY, brute-force implementation

(define (GET-MOVES state)
  (cond ((equal? (list-ref state 0) 'space) (list (list (swap state 0 1) 1) 
                                                  (list (swap state 0 3) 1)))
        ((equal? (list-ref state 1) 'space) (list (list (swap state 1 0) 1)
                                                  (list (swap state 1 2) 1)
                                                  (list (swap state 1 4) 1)))
        ((equal? (list-ref state 2) 'space) (list (list (swap state 2 1) 1)
                                                  (list (swap state 2 5) 1)))
        ((equal? (list-ref state 3) 'space) (list (list (swap state 3 0) 1)
                                                  (list (swap state 3 4) 1) 
                                                  (list (swap state 3 6) 1)))
        ((equal? (list-ref state 4) 'space) (list (list (swap state 4 1) 1)
                                                  (list (swap state 4 3) 1)
                                                  (list (swap state 4 5) 1)
                                                  (list (swap state 4 7) 1)))
        ((equal? (list-ref state 5) 'space) (list (list (swap state 5 2) 1)
                                                  (list (swap state 5 4) 1)
                                                  (list (swap state 5 8) 1)))
        ((equal? (list-ref state 6) 'space) (list (list (swap state 6 3) 1)
                                                  (list (swap state 6 7) 1)))
        ((equal? (list-ref state 7) 'space) (list (list (swap state 7 4) 1)
                                                  (list (swap state 7 6) 1)
                                                  (list (swap state 7 8) 1)))
        ((equal? (list-ref state 8) 'space) (list (list (swap state 8 5) 1)
                                                  (list (swap state 8 7) 1)))))


(define (swap lst index1 index2)
  (let ((val1 (list-ref lst index1)) (val2 (list-ref lst index2)))
    (replace (replace lst index1 val2) index2 val1)))

(define (replace lst index item)
  (if (= index 0)
      (cons item (cdr lst))
      (cons (car lst) (replace (cdr lst) (- index 1) item))))


(define (H state goalState)
  (cond ((null? state) 0)
        ((equal? (car state) (car goalState)) 
         (H (cdr state) (cdr goalState)))
        (else (+ 1 (H (cdr state) (cdr goalState))))))