;;; General data structures
(defstruct node
  state
  pred
  op
)

(defstruct problem
  initial-state
  operators
  goal-test
)

;;; 4-puzzle problem

(defun left (node)
  (setf loc (space-loc (node-state node)))
  (if (member loc '(1 3))
      (make-node :state (swap loc (- loc 1) (node-state node))))
  )
(defun right (node)
)
(defun down (node)
)
(defun up (node)
)

(defvar 4puzz)
(setf 4puzz
      (make-problem :initial-state '(1 2 - 3)
		    :operators (list #'left #'right #'down #'up)
		    :goal-test #'4goal))

;; problem describes the start state, operators, goal test, and operator costs
;; queueing-function is a comparator function that ranks two states
;; general-search returns either a goal node or failure

(defun general-search (problem q-fn)
  (setf nodes (list (make-node (problem-initial-state problem))))
  (while t 
    do (progn
	 (if (null nodes) (return-from 'general-search "failure"))
	 (setf node (pop nodes))
	 (if (funcall (goal-test problem) (node-state node))
	     (return-from 'general-search node))
	 (setf nodes (funcall q-fn nodes 
			      (expand node (problem-operators problem)))))))


(defun expand (node operators)
  (mapcan #'(lambda (op) (funcall op node))
	  operators)
  )

;;; QUEUING FUNCTIONS

(defun bfs-q (nodes new-nodes)
  (append nodes new-nodes))

(defun dfs-q (nodes new-nodes)
  (append new-nodes nodes))

(defun space-loc (state)
  (loop for i from 0 to (- (length state) 1)
    do (if (eq (nth i state) '-) (return-from space-loc i)))
  (error "can't find space in ~s!!!" state))

(defun swap (i j state &aux temp)
  (setf temp (nth i state))
  (setf (nth i state) (nth j state))
  (setf (nth j state) temp))