;;; Partially written code to allow study of the A* algorithm on the 8-puzzle
;;; in conjuction with the code in a-star.lisp.
;;;
;;; a b c        represented as (a b c d e f g h i)
;;; d e f
;;; g h i
;;;
;;; 0 denotes blank
;;;
;;; That is, the position in the list corresponding to each tile position is
;;; 
;;; 0 1 2
;;; 3 4 5
;;; 6 7 8

;;; Each element of the list returned has the form (state . 1), where the
;;; second element 1 of the dotted pair indicates the cost of making the
;;; move to that state, as needed for the A* code appearing in a-star.lisp.

(defun successors (state)
  (let* ((blank-pos (position 0 state))
	 (neighbors (case blank-pos
			  ((0) '(1 3))
			  ((1) '(0 2 4))
			  ((2) '(1 5))
			  ((3) '(0 4 6))
			  ((4) '(1 3 5 7))
			  ((5) '(2 4 8))
			  ((6) '(3 7))
			  ((7) '(4 6 8))
			  ((8) '(5 7)))))
    (mapcar #'(lambda (pos)
		(let ((succ (copy-list state)))
		  (setf (nth blank-pos succ) (nth pos succ))
		  (setf (nth pos succ) 0)
		  (cons succ 1)))
	    neighbors)
    ))

;;; To be complete, also need an appropriate state equality predicate and
;;; an appropriate heuristic distance function.  As an aid in computing the
;;; manhattan distance heuristic function, it is useful to be able to pass
;;; easily between the 1-dimensional indexing used above and the desired
;;; 2-dimensional indices.  These next two functions are designed to do this.
;;; Each row number, column number and one-dimensional index is zero-based.

(defun one-dimensional-index (row col)
  (+ col (* 3 row)))

(defun two-dimensional-indices (pos)
  (multiple-value-bind (row col)
		       (floor pos 3)
    (list row col)))