eyeprolog

Towers of Hanoi

How do you move a tower of three disks, one disk at a time?

The classic puzzle, solved by a two-clause recursion that mirrors the way people explain it: move the smaller tower aside, move the largest disk, move the smaller tower back on top.

Run it in the playground · Source

The question

Three pegs, a stack of disks on the left peg, largest at the bottom. Move the whole stack to the right peg, one disk at a time, never putting a larger disk on a smaller one. What is the sequence of moves?

The rules

hanoi(0, _from, _to, _via, []).
hanoi(N, From, To, Via, Moves) :-
  (N > 0),
  (N1 is N - 1),
  hanoi(N1, From, Via, To, Before),
  hanoi(N1, Via, To, From, After),
  append(Before, [[From, To]|After], Moves).

answer(3, Moves) :-
  hanoi(3, left, right, center, Moves).

Moving zero disks takes no moves. Moving N disks means: move N-1 to the spare peg (Before), move the largest disk [From, To], then move the N-1 disks on top of it (After). The disk count goes down on every call, so the recursion ends.

The answer

eyeprolog examples/hanoi.pl

answer(3, [[left, right], [left, center], [right, center], [left, right], [center, left], [center, right], [left, right]]).

Seven moves; the fourth, [left, right], is the largest disk.

The reason

step(hanoi(3, left, right, center, [[left, right], [left, center], [right, center], [left, right], [center, left], [center, right], [left, right]]),
     rule(2),
     ['N' = 3,
      'From' = left,
      'To' = right,
      'Via' = center,
      'Moves' = [[left, right], [left, center], [right, center], [left, right], [center, left], [center, right], [left, right]],
      'N1' = 2,
      'Before' = [[left, right], [left, center], [right, center]],
      'After' = [[center, left], [center, right], [left, right]]],
     ...

The step for three disks shows the split: three moves to park two disks on the centre peg, the big move, then three moves to bring them over.

The check

condition('C1', resolution, ok, 10).
condition('C5', re_decision, ok, 12).
verdict(checked).

The 10 rule steps replay against hanoi/5 and answer/2. The 12 built-in steps (the > tests, the is subtractions, and the append/3 calls) were recomputed independently and agreed. Nothing is trusted.

Try it

Add answer(4, Moves) :- hanoi(4, left, right, center, Moves). and count the moves. (15, that is 2⁴ − 1.)
Why does the recursive clause need N > 0? Remove it and ask for hanoi(1, left, right, center, M).

Learn more in The Art of EyeProlog, Chapter 19.

This site is open source. Improve this page.