%% 
%% part3.pl (Towers of hanoi in prolog)
%% Author: 
%% 
%%

%% A good place to start is with the
%% code in spam.pl (covered in class)

%% The representation of the towers-of-hanoi
%  game will be a list of three lists of integers
%
%  Each integer represents a disk whose radius is the integer's value
%
%  Within the overall configuration, each of the three lists 
%  represents the three pegs of the game and which disks they hold.
%  The first element represents the top disk, the second element
%  is the second-from-top disk, and so on. [] is an empty peg.
%
%  Remember that larger disks can not be placed on smaller disks!


%% This problem can take advantage of
%
%  assert and retract
%
%  After solving, you will need to use retractall( marked(_) )
%  -- or its equivalent -- in order to "clean the slate" for
%  using this to solve subsequent instances of the problem...

% Here, we declare marked to be a 1-argument dynamic predicate:
:- dynamic marked/1.


%% These rules are provided in case they're of use...

% remove an element (which much be present) from a list...
remove(X,[X|R],R).
remove(X,[F|R],[F|S]) :- remove(X,R,S).

% generates permutations of the first input's list
perm([X|Y],Z) :- perm(Y,W), remove(X,Z,W).   
perm([],[]).

% checks if the input list is sorted
sorted( [] ).
sorted( [_] ).
sorted( [F,S|R] ) :- sorted( [S|R] ), F < S.

% binds the second argument to a sorted version of the first
mysort( [], [] ).
mysort( L, S ) :- perm( L, S ), sorted(S).