Prolog Learnings: The Tower of Hanoi

February 8, 2021 8-minute read

A recursive implementation of the Tower of Hanoi in Prolog.

This particular implementaion of the Tower of Hanoi is taken from Peter Flach’s book "Simply Logical: Intelligent Reasoning by Example", published in 1994 by Wiley. Also available online^[1]. And see Section 1.3 of Jeff Erickson’s book "Algorithms"^[2].

The Tower of Hanoi^[3] is a well known puzzle in computer science where finding a solution seems most suited to a recursive rather than iterative algorithm. Three pegs, left, middle, and right where a set of disks on the left peg are stacked in decreasing size - smallest disk on top. The goal is to move the discs to the right peg, one disk at a time, such that no larger disk is ever placed on a smaller disk.

The algorithm is implemented in only eight lines but I still took a good few hours to really understand how the code works. This blog post is an attempt to explain the solution.

Prolog implementation from "Simply Logical: Intelligent Reasoning by Example"

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
:-op(900,xfx,to).

% hanoi(N,A,B,C,Moves) <-Moves is the list of moves to
%                        move N disks from peg A to peg C,
%                        using peg B as intermediary peg

hanoi(0, _A, _B, _C, []).
hanoi(N, A, B, C, Moves):-
      N > 0,
      N1 is N - 1,
      hanoi(N1, A, C, B, Before),
      hanoi(N1, B, A, C, After),
      append(Before, [A to C | After], Moves).

The hanoi predicate is defined as hanoi(N, A, B, C, Moves)

1
?- N = 3, A = left, B = middle, C = right, hanoi(N, A, B, C, Moves).

N contains the number of discs on the peg.
A, B, and C are the three pegs, each of which may contain any of the named pegs left, middle and right respectively (or middle, left and right, etc.)
Moves contains a list of moves to get the discs from peg A to peg C using peg B as the intermediary.

Lets start by defining the base case which N is zero and there are no more discs to move, so Moves should return an empty list as there are no moves to make.

Always define the base case first as this terminates the recursive algorithm.

We define a predicate that will match only for 0 discs and return an empty list of Moves

1
hanoi(0, _A, _B, _C, []).          % (1)

1	Underscore instantiates an anonymous variable. Any variable name after the underscore is just for readability purposes.

Test by calling hanoi with N = 0 and see if Moves contains an empty list…

1
2
3
4
?- N = 0, hanoi(N, left, middle, right, Moves).

N = 0,
Moves = []

…which it does.

Now that the zero disc base case is handled, lets tackle one disk. The single disc case can be solved by moving the disc on the left peg directly to the disc on the right (Moves = [Left to Right]).

Figure 1. "One Disc"

But looking ahead to solving for two discs we know that we need to use the middle peg as an intermediary. As shown below in the sequence of moves for two discs, we have to move Left to Middle peg, before we can move Left to Right peg, finally moving Middle to Right peg.

Figure 2. "Two Discs"

Lets not worry about how to implement the Left to Middle, and Middle to Right moves now. It is sufficient to know that there needs to be a Before and After list of moves which can be solved recursively by calling hanoi for each, as can be see in the following diagram.

Figure 3. "Recursive Overview"

Prolog code (Elixir and Erlang are similar) is generally written to avoid if/else or switch/case statements by taking advantage of Prolog’s capability to pattern match on predicate arguments. Avoiding the traditional if/else and switch/case style of conditional logic by making use of argument pattern matching means a predicate handles only one condition. Supporting new conditions involves adding new code and not modifing existing code. We add a second predicate that matches for N - 1 number of pegs after the base case. The base case must be defined first in the code because of Prologs evaluation rules.

1
2
3
4
5
6
7
8
9
:-op(900,xfx,to).

hanoi(0, _A, _B, _C, []).                         % (1)
hanoi(N, A, B, C, Moves):-
      N > 0,                                      % (2)
      N1 is N - 1,                                % (3)
      hanoi(N1, A, B, C, Before),                 % (4)
      hanoi(N1, A, B, C, After),                  % (5)
      append(Before, [A to C | After], Moves).    % (6)

1	The base case that terminates recursion when the number of discs reaches zero. No moves, so an empty "Moves" list is returned.
2	This test guards against N going negative due to backtracking if Prolog is asked to find alternate solutions.
3	Move closer to the base case by decreasing the number of discs with each call to hanoi.
4	Solving for the Before moves.
5	Solving for the After moves.
6	Prepend the list of Before moves and append the After moves to the "left to right" move.

The append(Before, [A to C | After], Moves) creates a new list of Before + [A to C] + After and unifies this new list with Moves.

Lets attempt to solve for a single disc.

1
2
3
4
?- N = 1, hanoi(N, left, middle, right, Moves).

N = 1,
Moves = [left to right]

[A to C] is unifed to [left to right], as left and right are the values of A and C that are passed into hanoi. Calling hanoi with N1 = 0 matches the base so Before and After return a list of empty moves ([]), thus append([], [left to right | []], Moves).

Figure 4. "Recurse One Disc"

And most importantly, our code terminates and does not enter a recursive loop and blow the stack.

What happens when we call N = 2?

1
2
3
4
?- N = 2, hanoi(N, left, middle, right, Moves).

N = 2,
Moves = [left to right, left to right, left to right]

This solution obviously is not correct, but at least we have a list of Before and After moves.

Lets look at the two disc case. When we call hanoi the fist time, we pass A = left, B = middle, C = right. In the append we see the [A to C|…] which unifies to [left to right]. hanoi always unifies the current move as [A to C], which means we will need to change the order of the pegs when we call hanoi to create a Before move of [left to middle], and an After move of [Middle to Right].

Changes to support N - 1 discs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
:-op(900,xfx,to).

% hanoi(N,A,B,C,Moves) <-Moves is the list of moves to
%                        move N disks from peg A to peg C,
%                        using peg B as intermediary peg

hanoi(0, _A, _B, _C, []).
hanoi(N, A, B, C, Moves):-
      N > 0,
      N1 is N - 1,
      hanoi(N1, A, C, B, Before),               % (1)
      hanoi(N1, B, A, C, After),                % (2)
      append(Before, [A to C | After], Moves).

1	Move from left (`A`) to middle (`B`) pegs.
2	Move from middle (`B`) to right (`C`) pegs.

For the Before list of moves we swap C and B, hanoi(N1, A, C, B, Before) which will unify to hanoi(N1, left, right, middle, Before). So Before will return [left to middle].

For the After list of moves we swap B and A, hanoi(N1, B, A, C, After) which will unify to hanoi(N1, middle, left, right, After). So After will return [middle to right].

Thus, append(Before, [A to C | After], Moves) is unifed to append([left to middle], [left to right | [middle to right]], Moves).

Figure 5. "Recurse Two Discs"

Now, solving for two discs creates the correct list of moves

1
2
3
4
?- N = 2, hanoi(N, left, middle, right, Moves).

N = 2,
Moves = [left to middle, left to right, middle to left]

Three discs looks a lot more complicated, as show in in the following figure. Here the sequence of Moves is Left to Right, Left to Middle, Right to Middle, Left to Right, Middle to Left, Middle to Right, Left to Right. We can see that discs are being moved in both directions.

Figure 6. "Three Discs"

So how do we go about defining the use case for three discs? Well, as it turns out we don’t need to

1
2
3
4
5
6
7
?- N = 3, hanoi(N, left, middle, right, Moves).

N = 3,
Moves = [Left to Right, Left to Middle,
         Right to Middle, Left to Right,
         Middle to Left, Middle to Right,
         Left to Right]

Our existing code that handles two discs handles three discs just fine. In fact, the code handles N - 1 discs. Try it out. But keep in mind that the "Big O" complexity for Tower of Hanoi is exponential, so things slow down fast for a number of discs greater than N = 20. Recursion is pretty incredible.

Finally, the code reads a little easier when the pegs A, B, C are changed to Src, Tmp and Dst

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
:-op(900,xfx,to).

% hanoi(N, Src, Tmp, Dst, Moves) <-Moves is the list of moves to
%                                  move N disks from peg Src to peg Dst,
%                                  using peg Tmp as intermediary peg

hanoi(0, _Src, _Tmp, _Dst, []).
hanoi(N, Src, Tmp, Dst, Moves):-
      N > 0,
      N1 is N - 1,
      hanoi(N1, Src, Dst, Tmp, Before),               % (1)
      hanoi(N1, Tmp, Src, Dst, After),                % (2)
      append(Before, [Src to Dst | After], Moves).

Figure 7. "Recurse Three Discs"

1. https://book.simply-logical.space/part_ii.html#reasoning_with_structured_knowledge

2. https://jeffe.cs.illinois.edu/teaching/algorithms/

3. https://en.wikipedia.org/wiki/Tower_of_Hanoi