Description:This was written for an undergraduate course in Artificial Intelligence.
This particular piece of code was written in Lisp to solve the Tower of Hanoi problem.
(defun in(obj list)
"is 'obj' in 'list'?"
(loop for i in list do
(if (equal obj i) (return T))
)
)
(defun move(peg to state)
"Move the disk on peg 'peg' to peg 'to' in 'state'"
(push (pop (nth peg state)) (nth to state))
(return-from move state)
)
(defun options(peg board)
"Search for possible options for moving the disk from 'peg'."
(if (null (first (nth peg board))) (return-from options nil))
(setq result nil)
(loop for i from 0 below (length board) do
(if (not (eq i peg))
(if (or (null (first (nth i board))) (< (first (nth peg board)) (first (nth i board))))
(push (move peg i (copy-list board)) result)
)
)
)
(return-from options result)
)
(defun Tower-Of-Hanoi(InitialState GoalState)
"Breadth-first search the tower of hanoi problem from an 'InitialState' to a 'GoalState'"
(cond ((null InitialState) nil)
((null GoalState) nil)
((not (eq (length InitialState) (length GoalState))) nil)
(t (setq solution ())
(setq frontier (list InitialState))
(setq explored ())
(loop while (not (null frontier)) do
;(print "frontier:")
;(print frontier)
(setq node (pop frontier))
(push node explored)
;(print "explored:")
;(print explored)
(loop for j from 0 below (length InitialState) do
(loop for option in (options j node) do
(if (equal option GoalState) (return-from Tower-Of-Hanoi (format nil "Solution found: frontier size is (~D), explored size is (~D)" (length frontier) (length explored))))
(if (not (or (in option frontier) (in option explored)))
(setq frontier (append frontier (list option)))
)
)
)
)
)
)
)
(defun my-print(list)
"Print a nice version of the states in 'list'"
(loop for i in list do
(print i)
)
)
(Tower-Of-Hanoi '((1 2 3) () ()) '(() () (1 2 3)))
(my-print frontier)
(my-print explored)