Solving the Towers of Hanoi Problem using State Space Search
The Towers of Hanoi problem can he described as follows:
• There are three pegs, labelled A, B, and C.
- There are 3 disks on peg A. The top disk has a diameter of 1, the middle disk has a diameter of 2, and the bottom disk has a diameter of 3.
- There are no disks on peg B or peg C.
- You must move one disk at time and you cannot place a larger disk on top of a smaller disk.
- The problem is to get all of the disks on peg C.
While various techniques can be used to solve this problem (recursion being the most popular) for this assignment you must use state space search.
State Representation:
A state is to be represented as a list of three (sub) lists-one for each peg. If a peg contains no disks, then the list for that peg is empty: otherwise the list contains a sequence of numbers that indicates which disks are on that peg from top to bottom Number 1 corresponds to the smallest disk; number 2 corresponds to the second smallest disk and so on. Thus, for the Initial State shown above, the lists for pegs A, B and C are respectively (1 2 3), (), and (). The start state is represented as the list containing these three lists; i.e., as the list ((1 2 3) () ()).
Writing the code:
Work through the following:
1. Create a global variable *start-state*, whose value represents the initial stare. Initialize it to the start state.
2. Create a global variable *goal-state*, whose value represents the goal state. Initialize it to the goal state.
3. Write a lisp predicate legal-move?, that takes two arguments-from and to-which are the lists corresponding to source and destitution pegs for a possible move. The predicate should return T if the top disk on from may legally be moved to to, and nil otherwise. Here are a couple of test case, but you should create as many additional test cases as you need in order to be confident that your predicate operating correctly:
>(legal-move? '(1 3) ' (2))
T
(A disk maybe placed on top of a larger disk)
>(legal-move? ' (3) ' (1 2))
NIL
(A disk may not be placed on top of a smaller disk)
4. Create a function move-A-to-B that takes a state as input. If the top disk from peg A cannot be moved legally to peg B the function should returns nil; otherwise. It should return the state resulting from moving the top disk from peg A to peg B. Note that the function move-A-to-B takes a state as an argument, and returns either nil or a new state: i.e., it does not modify its argument.
> (move-A-to-B ' ((1) (2 3) ()))
(NIL (1 2 3) NIL)
> (move-A-to-B ' ((1 3) (2) ()))
(3 (1 2) NIL)
> (move-A-to-B ' (() (1) (2 3)))
NIL
> (move-A-to-B ' ((3) (1) (2)))
NIL
Again, create as many additional test cases as you need in order to be confident that your function sis operating correctly.
Note: It is generally not good considered good practice to use Lisp primitives such as list, nth, etc., to directly create list, or to access elements of lists. It is much better style to define your own problem-specific functions to create and access stats, and to then use these within your functions. As an example, consider the functions make-state, farmer-side, etc., that we used in the farmer-wolf-goat-cabbage problem. If you used primitives such as list or nth in your Implementation of move-A-to-B, then you should rewrite this function to make use of problem-specific functions.
5. Define Lisp functions for the other required operators.
6. Create a global variable *operators* to store the name of each operator. Initialize it appropriately.
7. Define a predicate solution-state? that takes a state as argument and returns T if that state is the solution state.
8. Perform breadth-first search using the Lisp search code that has been supplied.