;;Solution for the 8-puzzle problem using the A* search algorithm. 
;;Author : Jeffrey John, Anthony Jose, Nipun Bhatia and Karthik V. 
;;30/03/2011

;;Swap function
(defun swap (ip_list pos1 pos2) 
(setf temp (nth (- pos1 1) ip_list))
(setf (nth  (- pos1 1) ip_list) (nth (- pos2 1) ip_list)) 
(setf (nth  (- pos2 1) ip_list) temp)
(setf (nth 10 ip_list) pos2)
(if t ip_list ))

;;LEFT
(defun move_left (ip_list)
 (setf pos (nth 10 ip_list))
 (if (not (or (eq pos 1) (eq pos 4) (eq pos 7))) (swap ip_list pos (- pos 1))))    
 
 ;;RIGHT
(defun move_right (ip_list)
 (setf pos3 (nth 10 ip_list))
 (if (not (or (eq pos3 3) (eq pos3 6) (eq pos3 9))) (swap ip_list pos3 (+ pos3 1))))
 
 ;;TOP
(defun move_top (ip_list)
 (setf pos4 (nth 10 ip_list))
 (if (not (or (eq pos4 1) (eq pos4 2) (eq pos4 3))) (swap ip_list pos4 (- pos4 3))))
 
 ;;BOTTOM
(defun move_bottom (ip_list)
 (setf pos5 (nth 10 ip_list))
 (if (not (or (eq pos5 7) (eq pos5 8) (eq pos5 9))) (swap ip_list pos5 (+ pos5 3))))
 
;;COMPUTE_SET_HEURISTIC 
(defun cs_heuristic (ip_list) 
(setf temp (copy-list ip_list))
(setf goal_list '(1 2 3 8 - 4 7 6 5))
(setf count 0)
(dotimes (n 9)
(if (equal (first goal_list) (first temp)) (setf count (+ count 0)) (setf count (+ count 1)))
(setf temp (rest temp))
(setf goal_list (rest goal_list)))
(setf (nth 9 ip_list) count)
(if t ip_list ))

;;COMPUTE_MIN
(defun compute_min (ip_list)
(setf length1 (list-length ip_list))
(setf temp2 ip_list)
(setf min 12)
(dotimes (n length1)
(if (> min (nth 9 (first temp2))) (setf min (nth 9 (first temp2))))
(setf temp2 (rest temp2)))
(if t min ))

;;CLEAN_LIST
(defun clean_list (ip_list)
(setf length2 (list-length ip_list))
(setf temp3 ip_list)
(setf cl_list '())
(setf min (compute_min temp3))
(dotimes (n length2)
(if (equal min (nth 9 (first temp3))) (setf cl_list (append cl_list (list (first temp3)) )))
(setf temp3 (rest temp3)))
(if t cl_list))

;;CHECK_GOAL
(defun check_goal (ip_list)
(setf length3 (list-length ip_list))
(setf temp4 (copy-list ip_list))
(setf goal_list '(1 2 3 8 - 4 7 6 5 0 5))
(dotimes (n length3)
(if (equal goal_list (first temp4)) (return t))
(setf temp4 (rest temp4)))
)
 
;;OP
(defun op (ip_list)
(setf length4 (list-length ip_list))
(setf temp5 ip_list)
(setf new_list '())
(dotimes (n length4)
(setf k1 (copy-list (move_left (first temp5))))
(if (not (equal k1 nil)) (setf k2 (copy-list (move_right (move_right (first temp5))))) (setf k2 (copy-list (move_right (first temp5)))) )
(if (not (equal k2 nil)) (setf k3 (copy-list (move_top (move_left (first temp5)))))    (setf k3 (copy-list (move_top (first temp5)))) )
(if (not (equal k3 nil)) (setf k4 (copy-list (move_bottom (move_bottom (first temp5))))) (setf k4 (copy-list (move_bottom (first temp5)))))
(if (not (equal k1 nil)) (setf new_list (append new_list (list k1))))
(if (not (equal k2 nil)) (setf new_list (append new_list (list k2))))
(if (not (equal k3 nil)) (setf new_list (append new_list (list k3))))
(if (not (equal k4 nil)) (setf new_list (append new_list (list k4))))
(setf temp5 (rest temp5)))
(if t new_list))

;;CS_HEURISTIC MAIN
(defun csh_main (ip_list)
(setf length5 (list-length ip_list))
(setf new_list '())
(setf temp6 ip_list)
(dotimes (n length5)
 (setf new_list (append new_list (list (cs_heuristic (first temp6)))))
 (setf temp6 (rest temp6)))
 (if t new_list))

;;OP_MASTER
(defun op_master (ip_list)
(if (check_goal ip_list)  (progn (print ip_list) (return-from op_master t)))
(if (equal ip_list nil)  (return-from op_master nil)
 (progn (print ip_list) (return-from op_master (op_master (clean_list (csh_main (op ip_list))))) )))