Prolog - Towers of Hanoi

Question

I'm trying to write a program to solve the towers of hanoi problem in Prolog. None of the posts here helped me so I decided to ask for myself. I have written the following code. It works well for 2 disks but goes into an infinite loop for 3.

hanoi(1,A,B,_,[(A,B)]).
hanoi(X,A,B,C,Y):-
  hanoi(X2,A,C,B,Y1),
  hanoi(1,A,B,_,[Y2]),
  hanoi(X2,C,B,A,Y3),
  append(Y1,[Y2|Y3],Y),
  X2 is X-1.

It is called in the following way:

?- hanoi(3, a, b, c, Y).

a,b,c are the pegs. 3 is the number of disks and X is where we want the result.

I need to get the result in Y. I'm trying to recursively find the moves for X-1 discs from peg 1 to 3 using 2, 1 disc from peg 1 to 2, X-1 discs from peg 3 to 2 and append them. I can't understand what I'm doing wrong. Any help or guidance would be appreciated! Thanks!

Answer 1

The obvious problem -

When you have a conjunction, like:

a, b, c

You have two readings of this, logical and procedural. The logical reading would be:

"The conjunction is true if a is true, and b is true, and c is true."

The procedural reading is:

"The conjunction will succeed if a is evaluated and succeeds, then b is evaluated and it also succeeds, and then c is evaluated and it also succeeds." (or, to put it in other words, do a depth-first search of the solution space)

If you are careful enough, the procedural reading is not necessary to argue about your code. However, this is only the case when all subgoals in the conjunction have full overlap of the logical and the procedural reading.

The offender here is is/2. It does not have a purely logical meaning. It evaluates the right-hand operand (the arithmetic expression) and unifies the result with the left-hand (usually an unbound variable).

Here, you have a conjunction (in the body of the second clause) that says, in effect, "evaluate a(X), then, if it succeeds, find the value of X". The obvious problem is that a(X) requires the value of X to be evaluated in such a way that it terminates.

So, move the is before all subgoals that use its result, or look into using constraints.