# [Prolog] Tower of Hanoi – M discs & N poles version

The Tower of Hanoi (also called the Tower of Brahma or Lucas’ Tower, and sometimes pluralized) is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

- Only one disk can be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
- No disk may be placed on top of a smaller disk.

(Source: Wikipedia)

Here I use the state space search method, you may want to read [Prolog] State space search method before continuing. Each state in the state space is represented by a list in Prolog in below structure:

[D_{1}, D_{2}, … , D_{m}]

So D_{i} is the pole index that the i-th disc is lying on (1 <= i <= m). If the problem has n poles then: 1 <= D_{i} <= n. Beside, if i < j then the i-th disc’s size will be smaller than the j-th disc’s.

The only valid action on this state space is moving a disc to another pole with some constraints:

- You cannot move the disc that is not lying at the top of the pole. => Choose disc has pole index first appeared in the list.
- You cannot move the disc to a pole that already has a disc with smaller size lying there. => Choose the pole has index never appeared in other smaller discs standing before the chosen disc.
- The target pole is not the same as the source pole.

And here is our f – state transfer predicate:

1 |
f1([A|T], [D|T], C) :- not(member(A, C)), nb_getval(pole, N), range(L1, 1, N), difference(L1, [A|C], L), member(D, L). |

- A is the source pole index of considering disc
- D is the destination pole index of considering disc.
- C is the collection of all pole indices of smaller discs standing before A.
*pole*is the global variable contains the number of poles (also the possible greatest pole index of the game): If the game has 3 poles then*pole*= 3. N is the local variable version of*pole*.- L1 is a list contains N elements that are [N,N-1,…,3,2,1] . For example: range(L, 1, 5) will have L = [5, 4, 3, 2, 1].
- L is a list contains all elements in L1 but not in [A|C] – all possible indices of poles that the considering disc can be moved to. For example: difference([7,3,5,8,9], [3,8], X) will have X = [7,5,9].

I will have a different article about the predicate *range*, *difference* and *removedup*. For the moment, I will only describe its function if necessary.

As you can see:

- The first constraint is satisfied by:

1not(member(A, C)) - Before continuing, I want to make an observation: If you run:

1member(X, [1,2,3]).

It will return X = 1 ; X = 2 ; X = 3.

The second and third constraints are then satisfied by:

1range(L1, 1, N), difference(L1, [A|C], L), member(D, L)

It means to choose a pole index that has never appeared before the considering disc. It also excludes the pole index that the considering disc is currently on.

May be we do not want to move the first disc in the list but also the other discs in the list with the same rules. Hence, we will use the list traversal technique:

1 |
f1([A|T], [A|T1], C) :- f1(T, T1, [A|C]). |

C parameter actually breaks our f(S, X) structure so we will wrap it up:

1 |
f([A|T], X) :- f1([A|T], X, []). |

Full program:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
f1([A|T], [D|T], C) :- not(member(A, C)), nb_getval(pole, N), range(L1, 1, N), difference(L1, [A|C], L), member(D, L). f1([A|T], [A|T1], C) :- f1(T, T1, [A|C]). f([A|T], X) :- f1([A|T], X, []). /*---------------------------------------------------------*/ s(S,E,P) :- s1(S,E,[S],P1), reverse(P1,P). s1(E,E,R,R). s1(S,E,R,P) :- f(S,X), not(member(X,R)), s1(X,E,[X|R],P). /*---------------------------------------------------------*/ /*All elements in S2 is excluded from S1.*/ difference1([],_,F,F). difference1([X|TX],Y,F,S) :- member(X,Y), difference1(TX,Y,F,S). difference1([X|TX],Y,F,S) :- not(member(X,Y)), difference1(TX,Y,[X|F],S). difference(S1,S2,S) :- removedup(S2,S2p), difference1(S1,S2p,[],S). /*---------------------------------------------------------*/ /*range(L,1,3) generates [3,2,1].*/ range(L, Low, High) :- range1([], L, Low, High). range1(L1, [High|L1], High, High). range1(L1, L, Low, High):- Low < High, Low1 is Low+1, range1([Low|L1], L, Low1, High). /*---------------------------------------------------------*/ /*remove duplicate elements in list I and return the output list O.*/ removedup(I, O) :- removedup1(I, O, []). removedup1([], L, L). removedup1([IH|IT], O, L) :- not(member(IH, L)), removedup1(IT, O, [IH|L]). removedup1([IH|IT], O, L) :- member(IH, L), removedup1(IT, O, L). |

Run the program:

1 2 |
nb_setval(pole, 3). s([1,1,1], [3,3,3], X). |