Optimizing Towers of Hanoi Puzzle with Heuristic Search

  • Thread starter Tony11235
  • Start date
In summary, the conversation discusses the Towers of Hanoi puzzle and the search for a decent heuristic to estimate the number of moves needed to reach the goal state of having all discs on the right-most post. The algorithm proposed involves stacking disks on an empty peg and using all available pegs to move them. The number of moves is shown to follow the triangular numbers pattern, and a heuristic of 1.35 times 3.34 to the square root of D is suggested. The conversation also mentions using this heuristic as part of an informed search, such as Best-First-Search or A* Search.
  • #1
Tony11235
255
0
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.
 
Physics news on Phys.org
  • #2
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),

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

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 [tex]1.35 \times 3.34^{\sqrt D}[/tex]

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.
 
Last edited:
  • #3
That [tex]1.35 \times 3.34^{\sqrt D}[/tex] 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 [itex]t_n = n(n+1)/2[/itex]

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

:cool:
 
  • #4
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.
 

1. What is the Towers of Hanoi heuristic?

The Towers of Hanoi heuristic is a mathematical puzzle that consists of three rods and a set of disks of different sizes. The objective of the puzzle is to move all the disks from one rod to another, with the constraint that a larger disk cannot be placed on top of a smaller disk. This puzzle is often used as a problem-solving exercise in computer programming and other fields.

2. How does the Towers of Hanoi heuristic work?

The Towers of Hanoi heuristic follows a set of rules to solve the puzzle. The first rule is that only one disk can be moved at a time. The second rule is that a disk can only be placed on top of a larger disk or an empty rod. The third rule is that larger disks must always be placed at the bottom of the stack. By following these rules, the puzzle can be solved in the minimum number of moves.

3. What is the optimal solution for the Towers of Hanoi heuristic?

The optimal solution for the Towers of Hanoi heuristic is to move all the disks from the starting rod to the target rod in the minimum number of moves possible. The minimum number of moves required to solve the puzzle is 2^n - 1, where n is the number of disks. This means that for 3 disks, the minimum number of moves required is 2^3 - 1 = 7.

4. What is the significance of the Towers of Hanoi heuristic?

The Towers of Hanoi heuristic is significant because it is a classic problem that has been used to demonstrate various concepts in mathematics, computer science, and other fields. It also serves as a good exercise for problem-solving and critical thinking skills.

5. How is the Towers of Hanoi heuristic used in computer science?

The Towers of Hanoi heuristic is often used in computer science as a benchmark for testing the efficiency and performance of algorithms. It is also used in the design and analysis of algorithms, as well as in teaching concepts such as recursion, divide and conquer, and complexity analysis.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
2
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
7K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
1K
  • Programming and Computer Science
Replies
5
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
11K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
3K
  • Classical Physics
Replies
15
Views
341
Replies
16
Views
1K
  • Math Proof Training and Practice
2
Replies
61
Views
9K
Replies
21
Views
1K
Back
Top