;;; Determines whether 2 configurations of the 8-puzzle can be reached
;;; from each other.  Approach is based on some theory that's beyond the
;;; scope of this class.
;;; 
;;; Configurations are represented as follows:
;;; 
;;; a b c        represented as (a b c d e f g h i)
;;; d e f
;;; g h i
;;;
;;; 0 denotes blank

(defun reachable? (s1 s2)
  (= (parity-invariant s1) (parity-invariant s2)))

(defun parity-invariant (state)
  (mod (tile-inversions state) 2))

(defun tile-inversions (state)
  (let ((non-blank-tiles (remove 0 state)))
    (count-inversions non-blank-tiles)))

(defun count-inversions (l)
  (cond ((null l) 0)
	(t (+ (how-many-less (first l) (rest l))
	      (count-inversions (rest l))))))

(defun how-many-less (x l)
  (count-if #'(lambda (y) (< y x)) l))