prologtowers-of-hanoi

How to keep Prolog from going back and forth between the same two steps forever?


Behold the following "solution" to the Towers of Hanoi problem:

f([],[],_).

f([A|As],[],C) :- f(As,[A],C).
f([A|As],B,[]) :- f(As,B,[A]).

f([],[B|Bs],C) :- f([B],Bs,C).
f(A,[B|Bs],[]) :- f(A,Bs,[B]).

f([],B,[C|Cs]) :- f([C],B,Cs).
f(A,[],[C|Cs]) :- f(A,[C],Cs).

f([A|As],[B|Bs],C) :- A < B, f(As,[A,B|Bs],C).
f([A|As],B,[C|Cs]) :- A < C, f(As,B,[A,C|Cs]).

f([A|As],[B|Bs],C) :- B < A, f([B,A|As],Bs,C).
f(A,[B|Bs],[C|Cs]) :- B < C, f(A,Bs,[B,C|Cs]).

f([A|As],B,[C|Cs]) :- C < A, f([C,A|As],B,Cs).
f(A,[B|Bs],[C|Cs]) :- C < B, f(A,[C,B|Bs],Cs).

But this will never finish as Prolog is getting stuck at moving disk 1 back and forth between rod A and B ad infinitum:

[trace]  ?- f([1,2,3],[],[]).
   Call: (10) f([1, 2, 3], [], []) ? creep
   Call: (11) f([2, 3], [1], []) ? creep
   Call: (12) f([3], [1], [2]) ? creep
   Call: (13) 3<1 ? creep
   Fail: (13) 3<1 ? creep
   Redo: (12) f([3], [1], [2]) ? creep
   Call: (13) 3<2 ? creep
   Fail: (13) 3<2 ? creep
   Redo: (12) f([3], [1], [2]) ? creep
   Call: (13) 1<3 ? creep
   Exit: (13) 1<3 ? creep
   Call: (13) f([1, 3], [], [2]) ? creep
   Call: (14) f([3], [1], [2]) ? creep
   Call: (15) 3<1 ? creep
   Fail: (15) 3<1 ? creep
   Redo: (14) f([3], [1], [2]) ? creep
   Call: (15) 3<2 ? creep
   Fail: (15) 3<2 ? creep
   Redo: (14) f([3], [1], [2]) ? creep
   Call: (15) 1<3 ? creep
   Exit: (15) 1<3 ? creep
   Call: (15) f([1, 3], [], [2]) ? creep
   Call: (16) f([3], [1], [2]) ? creep
   Call: (17) 3<1 ? creep
   Fail: (17) 3<1 ? creep
   Redo: (16) f([3], [1], [2]) ? creep
   Call: (17) 3<2 ? creep
   Fail: (17) 3<2 ? creep
   Redo: (16) f([3], [1], [2]) ? creep
   Call: (17) 1<3 ? creep
   Exit: (17) 1<3 ? creep
   Call: (17) f([1, 3], [], [2]) ? creep
   Call: (18) f([3], [1], [2]) ? 
   [...]

I'm generally aware of cuts being used in similar situations. But where would you place a cut here if that is required or indicated?

How to make this program finish without having to rearrange it based on specifics of the backtrack trace? Because I assume this would be an option here but this is of course a toy example.


Solution

  • You evidently want to define the search space by describing the legal moves and the final state, and let the search engine find its way to the solution on its own. But Prolog is a depth-first search engine, so it doesn't work here because, as coded, the search space has infinite depth, as you rightly note. The enumeration of attempted solution isn't "fair" since Prolog works in top-down left-to-right order which is what leads to it being "depth-first".

    A general answer to this is to use some kind of diagonalization of streams of partial solutions that can deal with infinite depth as well as infinite branching, to get a "fair enumeration" of solutions.

    Here though the branching, i.e. the number of legal moves from each legal position, is finite, so the simpler, breadth-first exploration is sufficient.

    So instead of coding the moves one by one, code up just one transition rule that turns a position into a list of all valid "next" positions. Then it's easy to code the breadth-first search with that.

    Just pop a position from an "agenda" list of positions to explore -- initially containing just one, starting position -- then turn that position to a list of its next positions, and append that list to the agenda, putting it at its end. This is what makes it breadth first, exploring the space level by level, so that the shortest path to the solution, if any, is found first.

    Prepending it at the start of the agenda list would result in the depth-first search again. Mixing the two up in some clever ways would make the search be clever, in some strange and clever way. Like if you had some heuristics, you could put the "better" solutions first.

    Instead of positions you can maintain the whole paths i.e. sequences of moves leading to each position, if needed.

    You'll still have to code it all yourself, since Prolog is a depth-first, top-down left-to-right search engine. It's a programming language, it is not a declarative programming system that would analyze your code by itself, and find ways to get to the solution by itself, a system that would be aware of its own computation processes and capable of adjusting itself, switching from depth first to breadth first or to diagonalization, all on its own, as one example. Prolog doesn't do that.