;;;  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 (swap state 0 1) (swap state 0 3)))
        ((equal? (list-ref state 1) 'space) (list (swap state 1 0) (swap state 1 2) 
                                                  (swap state 1 4)))
        ((equal? (list-ref state 2) 'space) (list (swap state 2 1) (swap state 2 5)))
        ((equal? (list-ref state 3) 'space) (list (swap state 3 0) (swap state 3 4) 
                                                  (swap state 3 6)))
        ((equal? (list-ref state 4) 'space) (list (swap state 4 1) (swap state 4 3) 
                                                  (swap state 4 5) (swap state 4 7)))
        ((equal? (list-ref state 5) 'space) (list (swap state 5 2) (swap state 5 4) 
                                                  (swap state 5 8)))
        ((equal? (list-ref state 6) 'space) (list (swap state 6 3) (swap state 6 7)))
        ((equal? (list-ref state 7) 'space) (list (swap state 7 4) (swap state 7 6) 
                                                  (swap state 7 8)))
        ((equal? (list-ref state 8) 'space) (list (swap state 8 5) (swap state 8 7)))))


(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 (HEURISTIC state goalState)
  (cond ((null? state) 0)
        ((equal? (car state) (car goalState)) 
         (+ 1 (HEURISTIC (cdr state) (cdr goalState))))
        (else (HEURISTIC (cdr state) (cdr goalState)))))