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.
According to /u/brebs something like this would be the most straightforward adaption of my code, keeping track of and avoiding past states. This does not just look ugly it is - if I dare to say - downright unmaintainable. Hence I hope some Prolog Yedi is taking notice of my plight and enlightens me as how to do it right.
f([],[],_,P,P).
f([A|As],[],C,P,P_) :-
\+ member([As,[A],C],P),
f(As,[A],C,[[As,[A],C]|P],P_).
f([A|As],B,[],P,P_) :-
\+ member([As,B,[A]],P),
f(As,B,[A],[[As,B,[A]]|P],P_).
f([],[B|Bs],C,P,P_) :-
\+ member([[B],Bs,C],P),
f([B],Bs,C,[[[B],Bs,C]|P],P_).
f(A,[B|Bs],[],P,P_) :-
\+ member([A,Bs,[B]],P),
f(A,Bs,[B],[[A,Bs,[B]]|P],P_).
f([],B,[C|Cs],P,P_) :-
\+ member([[C],B,Cs],P),
f([C],B,Cs,[[[C],B,Cs]|P],P_).
f(A,[],[C|Cs],P,P_) :-
\+ member([A,[C],Cs],P),
f(A,[C],Cs,[[A,[C],Cs]|P],P_).
f([A|As],[B|Bs],C,P,P_) :- A < B,
\+ member([As,[A,B|Bs],C],P),
f(As,[A,B|Bs],C,[[As,[A,B|Bs],C]|P],P_).
f([A|As],B,[C|Cs],P,P_) :- A < C,
\+ member([As,B,[A,C|Cs]],P),
f(As,B,[A,C|Cs],[[As,B,[A,C|Cs]]|P],P_).
f([A|As],[B|Bs],C,P,P_) :- B < A,
\+ member([[B,A|As],Bs,C],P),
f([B,A|As],Bs,C,[[[B,A|As],Bs,C]|P],P_).
f(A,[B|Bs],[C|Cs],P,P_) :- B < C,
\+ member([A,Bs,[B,C|Cs]],P),
f(A,Bs,[B,C|Cs],[[A,Bs,[B,C|Cs]]|P],P_).
f([A|As],B,[C|Cs],P,P_) :- C < A,
\+ member([[C,A|As],B,Cs],P),
f([C,A|As],B,Cs,[[[C,A|As],B,Cs]|P],P_).
f(A,[B|Bs],[C|Cs],P,P_) :- C < B,
\+ member([A,[C,B|Bs],Cs],P),
f(A,[C,B|Bs],Cs,[[A,[C,B|Bs],Cs]|P],P_).
At least it terminates with a solution.
?- f([1,2,3],[],[],[[[1,2,3],[],[]]],P), reverse(P,P_), write(P_).
[[[1,2,3],[],[]],[[2,3],[1],[]],[[3],[1],[2]],[[1,3],[],[2]],
[[1,3],[2],[]],[[3],[2],[1]],[[3],[1,2],[]],[[],[1,2],[3]],
[[1],[2],[3]],[[],[2],[1,3]],[[2],[],[1,3]],[[2],[1],[3]],
[[],[1],[2,3]],[[1],[],[2,3]],[[],[],[1,2,3]]]