hanoi
Figure 1. Towers of Hanoi: Initial and Goal Situation

The Towers of Hanoi puzzle features three pegs and four disks of varying sizes. The objective, as shown in Towers of Hanoi: Initial and Goal Situation, is to move all disks from the leftmost peg to the rightmost, following two rules: only the top disk on any peg can be moved, and a disk cannot be placed atop a smaller disk.

While efficient algorithms exist, here we use a declarative approach: instead of describing how to solve the puzzle step by step, we specify the conditions that define valid sequences of moves.

In Answer Set Programming (ASP), it’s customary to provide a uniform encoding that applies to any problem instance. Our task: given an initial disk arrangement, a goal configuration, and a number n, determine whether a sequence of n moves can achieve the goal. ASP and clingo can solve this elegantly.

Problem Instance

We describe the puzzle using facts over several predicates. Here’s what each means:

  • peg/1: Names of pegs (e.g., a, b, c)

  • disk/1: Disk numbers (smaller numbers represent larger disks)

  • init_on/2: Initial positions of disks

  • goal_on/2: Goal positions of disks

  • moves/1: Number of allowed moves

For the puzzle shown in Towers of Hanoi: Initial and Goal Situation, allowing 15 moves, the instance is described by:

peg(a;b;c).
disk(1..4).
init_on(1..4,a).
goal_on(1..4,c).
moves(15).

The ; in the first line is syntactic sugar, expanding to three facts: peg(a)., peg(b)., and peg(c). The interval 1..4 abbreviates four facts for disks 1 through 4.

These facts define the Towers of Hanoi instance in Towers of Hanoi: Initial and Goal Situation, with the requirement that the goal be reached within 15 moves.

Problem Encoding

Next, we encode the Towers of Hanoi using schematic rules—rules with variables (starting with uppercase letters) that generalize across instances. Typically, an encoding is divided into four logical sections:

  • Generate: Forms possible solutions

  • Define: Introduces auxiliary predicates

  • Test: Adds constraints to eliminate invalid solutions

  • Display: Controls output

Each part is marked with % comments:

% Generate
{ move(D,P,T) : disk(D), peg(P) } = 1 :- moves(M), T = 1..M.
% Define
on(D,P,0)   :- init_on(D,P).
on(D,P,T)   :- move(D,P,T).
on(D,P,T+1) :- on(D,P,T), not move(D,*,T+1), not moves(T).
blocked(D-1,P,T+1) :- on(D,P,T), not moves(T).
blocked(D-1,P,T)   :- blocked(D,P,T), disk(D).
% Test
:- move(D,P,T), blocked(D-1,P,T).
:- move(D,*,T), on(D,P,T-1), blocked(D,P,T).
:- goal_on(D,P), not on(D,P,M), moves(M).
:- { on(D,P,T) } != 1, disk(D), moves(M), T = 1..M.
% Display
#show move/3.

Variables D, P, T, and M stand for disks, pegs, move numbers, and the total number of moves.

Generate: The first rule uses a cardinality constraint: for each time point from 1 to M, it lists all possible moves and requires that exactly one is chosen. This means that at every step, exactly one disk is moved to some peg, generating all possible move sequences of length M.

Define: Auxiliary predicates describe properties of these sequences. For example, on/3 tracks where each disk is at each time. The rules specify how the initial state is set, how moves change disk positions, and how disks remain on pegs unless moved. The blocked/3 predicate marks for each peg all the disk indices that cannot be moved at a time point, which is useful for enforcing the puzzle’s rules.

Test: Constraints prevent invalid moves, such as placing a larger disk on a smaller one, moving blocked disks, failing to reach the goal, or having a disk on more than one peg at a time. The last constraint is redundant but helps the solver work more efficiently.

Display: The final line tells the solver to show only the moves (move/3) in the output, hiding auxiliary predicates and instance details for clarity.

Problem Solution

With the instance and encoding in place, we can solve the puzzle by running:

clingo instance.lp encoding.lp

The output of clingo should look like this:

clingo version 6.0.0
Reading from toh_ins.lp ...
Solving...
Answer: 1
move(4,b,1) move(3,c,2) move(4,c,3) move(2,b,4) \
move(4,a,5) move(3,b,6) move(4,b,7) move(1,c,8) \
move(4,c,9) move(3,a,10) move(4,a,11) move(2,c,12) \
move(4,b,13) move(3,c,14) move(4,c,15)
SATISFIABLE

Models   : 1+
Calls    : 1
Time     : 0.017s (Solving: 0.01s 1st Model: 0.01s Unsat: 0.00s)
CPU Time : 0.010s

The first line shows clingo's version. The next two lines indicate the solver’s progress: reading the input and starting the search. For small instances like this, solving is nearly instantaneous, but for larger problems, there may be a noticeable delay.

Answer: signals a solution (answer set) was found. The following line lists all moves (move/3), ordered by time point. For example, the first move transfers disk 4 to peg b, the second moves disk 3 to peg c, and so on. The backslash (\) at the end of a line means the list of moves continues on the next line. The order in which atoms appear is arbitrary and does not affect the meaning of the solution; the same applies to the order in which answer sets are found.

Below the solution, clingo reports the satisfiability status (SATISFIABLE means a solution exists), the number of answer sets found, calls, and timing statistics.

Trying It Yourself

Throughout this guide, we encourage you to try out the examples yourself. You can experiment with the encoding and solver directly in your browser using the interactive editor below. Click the play button in the top right to run the solver on the Towers of Hanoi problem, or modify the encoding to see how your changes affect the solution—all without any installation.

% Instance
peg(a;b;c).
disk(1..4).
init_on(1..4,a).
goal_on(1..4,c).
moves(15).

% Generate
{ move(D,P,T) : disk(D), peg(P) } = 1 :- moves(M), T = 1..M.

% Define
on(D,P,0)   :- init_on(D,P).
on(D,P,T)   :- move(D,P,T).
on(D,P,T+1) :- on(D,P,T), not move(D,*,T+1), not moves(T).
blocked(D-1,P,T+1) :- on(D,P,T), not moves(T).
blocked(D-1,P,T)   :- blocked(D,P,T), disk(D).

% Test
:- move(D,P,T), blocked(D-1,P,T).
:- move(D,*,T), on(D,P,T-1), blocked(D,P,T).
:- goal_on(D,P), not on(D,P,M), moves(M).
:- { on(D,P,T) } != 1, disk(D), moves(M), T = 1..M.

% Display
#show move/3.

  • CPU Time is not available when running in the browser, it is reported as N/A.

Summary

Solving the Towers of Hanoi puzzle involved:

  1. Providing facts to represent a specific instance.

  2. Supplying a general encoding applicable to any instance, with sections for generating candidates, defining properties, testing constraints, and projecting output.

  3. Using ASP tools to solve the instance, with the encoding reusable for future puzzles.

This approach demonstrates the power and flexibility of declarative problem solving in ASP.