Optimizing Towers of Hanoi Puzzle with Heuristic Search

[Tony11235]

For a P posts, D discs, Towers of Hanoi puzzle, does anybody know of a decent heuristic? Where given a state, give back a rough estimate of the number of moves away from the goal state, which in this case is having all the disks moved to the right most post?

I know that for a 3 posts, D disk problem, the shortest number of moves is given by 2^D - 1. , but that is not of much use here.

 

[AlephZero]

I played around with this for P = 4.

I thought a reasonable idea to move D disks was

1 Stack k < D disks on an empty peg using all 4 pegs.

2 Stack the remaining D-k disks on an empty peg using 3 pegs (you can't use the peg with the smaller disks already on it). This takes 2^{(D-k)}-1 moves.

3. Stack the k disks on top if the bigger ones using all 4 pegs again.

So if the number of moves for D disks is M(D),

M(D) = min_k\big(2M(k) + 2^{(D-k)}-1\big)

Evaluating this up to D = 40 showed that the relation between D and k followed the triangular numbers 1,3,6,10, 15,21 ... i.e. when D = 15 k = 10, when D = 21 k = 15, etc.

Curve fitting gave the number of moves as approx 1.35 \times 3.34^{\sqrt D}

This is completely different from the 3 pegs. The number of moves for 40 disks is 2817 for P=4 and about 5.5e11 for P=3!

I don't know if this is the optimum algorithm. It generalises to more than 4 posts (e.g. for 5 posts, stack k disks using 5 posts, m disks using 4 posts, D-k-m disks using 3 posts, find the minimum values of k and m) but I haven't played with P > 4.

 

[AlephZero]

That 1.35 \times 3.34^{\sqrt D} was based on too little data

An exact result for 4 pegs:

Let M(k) be the number of moves for k disks and 4 pegs using the algorithm above.

M(1) = 1
M(3) = 2*M(1) + 2^2 - 1 = 5
M(6) = 2*M(3) + 2^3 - 1 = 17
M(10) = 2*M(6) + 2^4 - 1 = 49
etc.

Define the n'th triangular number t_n = n(n+1)/2

Then M(t_n) = (n-1)2^n + 1 - proof by induction.

 

[Tony11235]

I'm trying to use a heuristic of this sort as part of an informed search, first Best-First-Search (aka greedy search), then A* Search. So that instead expanding all nodes, using a heuristic to decide which node is closest to the goal state and only expand that node. This is really not an accurate one, but since my problem states that the goal state is having all the discs arranged properly to the right-most post, I guess I can just check the end post of each node and go with the one that has the most so far. If the problem stated that the goal was for the discs to be moved to any other post, then this would be worthless of course.