# Understanding Recursion in the Tower of Hanoi solver

I am learning Prolog and attempt get a more detailed understanding of the Tower of Hanoi solver (as described by Fisher) in order to understand recursion better.

This post is a bit lengthy, but I don’t know how to describe my confusion more concise.

The code for the Hanoi solver is as follows (I added a print statement in the recursion to see better what’s happening):

move(1, X, Y, _) :-
write('  Move top disk from '), write(X), write(' to '), write(Y), nl.

move(N, X, Y, Z) :-
N>1,
M is N-1,
write('Level: '), write(N), nl,
move(M,X,Z,Y),
move(1,X,Y,_),
move(M,Z,Y,X).

This works fine. Let’s use N=3 for example to evaluate it:

?- move(3,left,right,center).
Level: 3
Level: 2
Move top disk from left to right
Move top disk from left to center
Move top disk from right to center
Move top disk from left to right
Level: 2
Move top disk from center to left
Move top disk from center to right
Move top disk from left to right
true

In order to really understand this, I attempted to write the recursion myself and in the recursion rule I came up with another order of the move statements:

move(N, X, Y, Z) :-
N>1,
M is N-1,
write('Level: '), write(N), nl,
move(M,X,Z,Y),
move(M,Z,Y,X),
move(1,X,Y,_).

Let’s run it again with N=3:

?- move(3,left,right,center).
Level: 3
Move top disk from left to right
Level: 2
Move top disk from left to center
Move top disk from left to right
Move top disk from right to center
Level: 2
Move top disk from center to right
Move top disk from center to left
Move top disk from left to right
true

When doing the moves it’s easy to see that these instructions are wrong. But why? I though I first always do the “real” move and then call the recursions.

Thanks for pointers!

Are you aware of the trace facilities built into SWI-Prolog?
I.e. trace/0 and gtrace/0

Thanks for the info.

I have started with trace. It is probably very powerful. But I’m not sure what the output means. I looked at SWI-Prolog – Manual, but lots of things are not clear to me. Is there a tutorial for trace somewhere?

I tried gtrace as well, but I get only Correct to: "trace"?. I am on macOS and have installed swi-prolog via brew. Do I need more for gtrace?

I don’t use macOS so can not help with that.

If you are trying to learn Prolog on your own then I would suggest

Yes. The brew version is rather basic. If I recall correctly, the Macports version has a variant to include the (X11) development tools. Otherwise install the binary and install XQuartz.

Thanks @jan. So I need an X11 server for the GUI? (Probably worth it not only for gtrace, but for help as well…)

Well, I actually have started with LPN! But I cannot see that it explains the output of trace or similar…

ps: As said i didi look at Trace Mode Example (which in my earlier post I didn’t title well), but was hoping for more beginenr details about the output.

Here is a list of StackOverflow answers noting trace. You will have to weed out the ones that are of no use but some of them should be of value.

Love the SO query - am already down a rabbit hole there… Thanks heaps!

Try this version of your code:

move2(1, X, Y, _) -->
['Move top disk from'-X-'to'-Y].

move2(N, X, Y, Z) -->
{N>1},
{M is N-1},
['Level':N],
move2(M,X,Z,Y),
move2(M,Z,Y,X),
move2(1,X,Y,_).

with the query:

phrase(move2(3,left,right,center),Moves), maplist(writeln,Moves).

It still gives a different answer, but it’s a bit different from what you got.

In general, it’s better to avoid IO for results and instead use an accumulator. (I used DCG notation because that’s an easy way to get an accumulator.)

Thank you very much for this, @peter.ludemann!

You give me lots of things to look into: phrase/2, accumulator, DCG notation

Will look check it out - on Monday!

(Without really understanding DCGs yet,) I have tried your DCG variant of the hanoi solver, but I don’t understand what benefit I have from the accumulator:

From what I can see the list Moves contains exactly the moves which are written out to stdout in the predicate version.

Do I miss something?

I guess that there is a general feeling that you shouldn’t mix pure functions and side effects. It is a matter of judgement where you draw the line. But in this case you have “side effect during computation” vs. “side effect free computation”. Especially in Prolog, where it is common to take advantage of backtracking and “generate-and-test” code, side effects really get in the way. If you know that you will not backtrack then it doesn’t make such a huge difference I guess.

Aha, I see the print statements are side effects, right?

Silly question, but how do I know whether the prolog system will backtrack or not?

No, not silly at all. It is maybe the single most important question when you are in the process of writing Prolog code.

I guess the answer is “you look at your code and make sure that it will not backtrack”. The non-determinism of Prolog code does not self-arise, you have to introduce it somehow. But this is a very large topic and I am not sure where to even start.

Ok, I leave it "for another life”,

I’ve put up a different version of this puzzle on Swish at SWISH -- SWI-Prolog for SHaring.

You get the solution with the query route(A).

It’s a lot more verbose because it’s a translation from a version used in Stanford University’s General Game Player course found at http://games.ggp.org/base/games/hanoi/hanoi.kif written in a Lisp-like logical programming language, which I’ve translated into SWI Prolog.

The idea is to write an AI application that reads in any game or puzzle written in “Game Description Language”, and I’ve put notes on what I’ve developed at PuzzleSolving - SWI-Prolog Wiki

My approach is “generate and prune” which requires a lot more code than puzzle specific solvers, but may be more novice friendly because it goes through quite a lot of Prolog basics.

I’ve put ye old “Wolf, Goat, Cabbage” puzzle at SWISH -- SWI-Prolog for SHaring which exactly the same code solves with route(A).

Oh no this is not how I meant it

@halloleo Boris nicely summarized what I was thinking.

In you case, there’s no backtracking; but if there were, your printed output and the list from the DCG would be different. (I eye-grepped my output with yours and thought that they were different)

But I think that @Boris understates how common backtracking is. For example:

p(1).
p(2).
q(X,M) :- p(X), 0 =:= X mod M.

with the query q(4,2) – this will first try p(1), which will fail 0=:=1 mod 2, backtrack to p(2) and succeed 0=:=2 mod 2.

So, what looks like “if-then-else” in conventional languages is often handled by either pattern matching (unification) or backtracking in Prolog.

well it is so easy to create choice points in Prolog, and it is such a big topic where those could come from, that I didn’t even try: