% file:    towers0.pl
% author:  keller
% purpose: pre-programmed solution in Towers of Hanoi

% towers(N, From, To, Moves) means that Moves is the list of
% moves to move N disks from stack From to stack To

towers(N, From, To, Moves) :- 
    towers(N, From, To, [], ReversedMoves),
    reverse(ReversedMoves, Moves).


% towers(N, From, To, Acc, Moves) means that Moves is the reverse of the list
% of moves to move N disks from stack From to stack To, with Acc being 
% the reverse of the accumulated moves going in (to avoid appending).

% towers(N, From, To, Acc, Moves).

towers(0, _, _, Acc, Acc).

towers(N, From, To, Acc, Moves) :- 
    other(From, To, Other),
    N1 is N - 1,
    towers(N1, From, Other, Acc, Moves1),
    towers(N1, Other, To, [[From, To] | Moves1], Moves). 

other(1, 2, 3).
other(2, 1, 3).
other(1, 3, 2).
other(3, 1, 2).
other(2, 3, 1).
other(3, 2, 1).

% simple test case

test(N, Moves) :- towers(N, 1, 3, Moves).

test(N) :- test(N, Moves),
           write(Moves),
           nl.    
    
test :- test(4).


% 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).

% 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.



reverse(L, M) :- reverse(L, [], M).

reverse([], M, M).
reverse([A | L], M, N) :- reverse(L, [A | M], N).


% demonstrate on an N-disk puzzle

demo(N) :-
    gen(N, Stack),
    Initial = [Stack, [], []],
    towers(N, 1, 3, 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).