Solving the Tower of Hanoi by using a good state space and then a search tree

Question

I want to solve the "Towers of Hanoi" problem by using a good "state space". Using an appropriate state space is a way that is suggested by some AI techniques. Having a good state space, I would then like to be able to build a search tree and then use some strategy like "DFS" (depth-first-search) to find a solution.

My problem is, I just don't know how to develop a good state space and then use it to build a search tree. Can anyone describe how to create a state space for the Tower of Hanoi problem? Then tell me how to build a search tree for that?

Answer 1

I suggest the following state space:

Assuming you have n bricks and 3 towers denoted by 0,1,2. Denote the current state by a n trinary numbers, for example (in the case n=9):

987654321
001102020 (current state)

meaning that brick 9,8,5,3 and 1 are in the 0:th tower. Brick 7 and 6 in the 1:th tower and brick 4 and 2 in the 2:nd tower.

This would give you a state space of size 3^n, which is not too large.

(This is only a partial answer. But every state-string will correspond to a legal state. That is to say,

1. in each tower the size of the bricks will decrase from bottom to top,

2. no brick will appear in two different towers.

I therefore think that the suggested state space is minimal. )