Hanoi.

The Towers of Hanoi is a mathematical puzzle and patience game. One of the towers consists of several discs, where the smaller discs lie on the larger ones. The new tower must again contain the same order of discs. The following rules apply: Only one disc may be moved at a time and a larger disc may never lie on a smaller one.

Initial state (with 3 rings):

Copy code to clipboard

Target state (with 3 rings):

Copy code to clipboard

To solve this in Prolog, the following strategy can be pursued

In the best case, a single disc must be moved from one tower to the destination tower. X is moved to Y. In the recursive case, N discs are moved from X to Y. To achieve this, the first N-1 discs are moved to another peg X. The last disc is moved from tower X to tower Y. Then the N-1 discs are moved from X to Y:

Copy code to clipboard

An example call with 3 discs looks as follows:

Copy code to clipboard

The output provides the required moves:

Copy code to clipboard

The game can be solved with infinitely many discs. Most often, between 7 and 9 discs are used. [Mi09]