% file:    towers.pro
% author:  Robert Keller
% purpose: depth-first search for solution in Towers of Hanoi

% towers([S1, S2, S3], Moves) will mean that Moves is a valid move sequence 
% that results in S1 and S2 being empty (so all disks are on S3).

towers(InitialState, Moves) :- towers(InitialState, [], Moves).


% towers([S1, S2, S3], Seen, Moves) means the same, except that Seen will be a 
% list of all previous states (to prevent infinite looping)

towers([[], [], _], _, []).	% final state

towers(Before, Seen, [Move | Moves]) :-
    nonMember(Before, Seen),
    move(Move, Before, After),
    towers(After, [Before | Seen], Moves).


% move([From, To], Before, After) means that a disk can be moved from stack
% From in state Before to stack To, resulting in state After

move([1, 2], [[F1 | R1], S2, S3], [R1, [F1 | S2], S3]) :- ok(F1, S2).
move([1, 3], [[F1 | R1], S2, S3], [R1, S2, [F1 | S3]]) :- ok(F1, S3).
move([2, 1], [S1, [F2 | R2], S3], [[F2 | S1], R2, S3]) :- ok(F2, S1).
move([2, 3], [S1, [F2 | R2], S3], [S1, R2, [F2 | S3]]) :- ok(F2, S3).
move([3, 1], [S1, S2, [F3 | R3]], [[F3 | S1], S2, R3]) :- ok(F3, S1).
move([3, 2], [S1, S2, [F3 | R3]], [S1, [F3 | S2], R3]) :- ok(F3, S2).


% ok(Disk, Stack) means that it is ok to move the indicated Disk onto Stack

ok(_, []).

ok(A, [B | _]) :- smaller(A, B).

smaller(A, B) :- A < B.


% nonMember(X, L) means that X is not a member of list L.

nonMember(X, L) :-
  \+ member(X, L).

member(X, [X | _]).

member(X, [_ | L]) :- member(X, L).
    

% simple test case

test :- towers([[1, 2, 3, 4], [], []], Moves),
        write(Moves),
        nl.    
    

% simulate the moves, for demonstration purposes

play(State, [], [State]).	% no moves left

play(Before, [Move | Moves], [Before | States]) :-
    move(Move, Before, After),
    play(After, Moves, States).

% demonstrate on an N-disk puzzle

demo(N) :-
    gen(N, Stack),
    Initial = [Stack, [], []],
    towers(Initial, Moves),
    play(Initial, Moves, States),
    show(States).


% gen(N, Stack) generates [1, 2, 3, ..., N]

gen(N, Stack) :- gen(1, N, Stack).

gen(K, N, []) :- K > N.

gen(K, N, [K | Stack]) :- 
    K1 is K+1,
    gen(K1, N, Stack).


% show(List) prints a list of states, one per line

show([]).
show([State | States]) :-
    write(State),
    nl,
    show(States).

demo :- demo(4).