%  =================================================================
%  ==                                                             ==
%  ==          An Introduction to ARTIFICIAL INTELLIGENCE         ==
%  ==                  Janet Finlay and Alan Dix                  ==
%  ==                       UCL Press, 1996                       ==
%  ==                                                             ==
%  =================================================================
%  ==                                                             ==
%  ==        chapter 3, pages 52-53:  hanoi search graph 1        ==
%  ==                                                             ==
%  ==            Prolog example, Alan Dix, August 1996            ==
%  ==                                                             ==
%  =================================================================

%  In this example and hanint.pl we look at two representations
%  of the search graph for the Towers of Hanoi problem.

%  In this file, we will look at an extensional representation
%  (that is listing all cases), whereas hanint.pl has an intensional 
%  (rule based) representation.

%  In both cases the state of the problem is be represented
%  by a list of lists of numbers, where each number stands for a ring,
%  a ring - the larger the number, the bigger the ring.
%  For example, the list:  [[1,3],[],[2]]
%  will represent the problem state:
%
%              |      |      |
%             ===     |      |
%           =======   |    =====
%        ------+------+------+------
%
%  Moves will be of the form move(From,To), where From and To
%  are numbers representing the towers.
%  For example,  move(1,3), will mean that the top ring from
%  the 1st tower is moved to the 3rd tower.
%  As only the top-most ring can move there is no reason to
%  say which ring on the tower we mean.

%  In this representation we will explicitly list all states
%  and moves between them:

%  To save having an enormous file, we will only deal with
%  the two ring problem as illustrated in figure 3.5.

%  top triangle from fig 3.5
hanoi_ext( move(1,2), [[1,2],[],[]], [[2],[1],[]]  ).
hanoi_ext( move(2,1), [[2],[1],[]],  [[1,2],[],[]] ).

hanoi_ext( move(1,3), [[1,2],[],[]], [[2],[],[1]]  ).
hanoi_ext( move(3,1), [[2],[],[1]],  [[1,2],[],[]] ).

hanoi_ext( move(2,3), [[2],[1],[]],  [[2],[],[1]]  ).
hanoi_ext( move(3,2), [[2],[],[1]],  [[2],[1],[]]  ).

%  bottom left triangle from fig 3.5

hanoi_ext( move(3,1), [[],[2],[1]],  [[1],[2],[]]  ).
hanoi_ext( move(1,3), [[1],[2],[]],  [[],[2],[1]]  ).

hanoi_ext( move(3,2), [[],[2],[1]],  [[],[1,2],[]] ).
hanoi_ext( move(2,3), [[],[1,2],[]], [[],[2],[1]]  ).

hanoi_ext( move(2,1), [[],[1,2],[]], [[1],[2],[]]  ).
hanoi_ext( move(1,2), [[1],[2],[]],  [[],[1,2],[]] ).

%  bottom right triangle from fig 3.5

hanoi_ext( move(2,1), [[],[1],[2]],  [[1],[],[2]]  ).
hanoi_ext( move(1,2), [[1],[],[2]],  [[],[1],[2]]  ).

hanoi_ext( move(2,3), [[],[1],[2]],  [[],[],[1,2]] ).
hanoi_ext( move(3,2), [[],[],[1,2]], [[],[1],[2]]  ).

hanoi_ext( move(1,3), [[1],[],[2]],  [[],[],[1,2]] ).
hanoi_ext( move(3,1), [[],[],[1,2]], [[1],[],[2]]  ).

%  links between the triangles to complete the hexagon shape
%  these are the moves that shift the larger rings

hanoi_ext( move(2,1), [[],[2],[1]],  [[2],[],[1]]  ).
hanoi_ext( move(1,2), [[2],[],[1]],  [[],[2],[1]]  ).

hanoi_ext( move(1,3), [[2],[1],[]],  [[],[1],[2]]  ).
hanoi_ext( move(3,1), [[],[1],[2]],  [[2],[1],[]]  ).

hanoi_ext( move(2,3), [[1],[2],[]],  [[1],[],[2]]  ).
hanoi_ext( move(3,2), [[1],[],[2]],  [[1],[2],[]]  ).


%  Believe me - I did this by hand - it is a lot of effort!

%  Also I'm not that confident I've got it right when I
%  finished, I really need to hand check EVERY rule.
%  Even worse, imagine I wanted to solve for three rings
%  or even four!

%  This listing of all cases is called an extensional
%  definition.  It is clearly impractical for large
%  problems.  In fact, in the magic squares examples
%  there is no list of all possible magic squares,
%  instead rules are given which generate them.
%  This is called an intensional definition and such
%  a representation of Towers of Hanoi is found in
%  hanint.pl.


%  RUNNING THIS CODE
%
%  hanoi_ext is not very exciting as it is simply a database of facts!
%  We can enquire of it things like:
%            hanoi_ext(move(From,To),[[1,2],[],[]],State).
%  This would tell us all single moves from the normal start state.
%  
%  A little more intersting is to look at multi-stage moves.
%  For example, try:
%            hanoi_ext(M1,[[1,2],[],[]],Mid), hanoi_ext(M2,Mid,State).
%
%  This will tell you all places you can get to in exactly two moves
%  from the start state.
%
%  If you allow Prolog to tell you all such moves, you will find it
%  includes the start state itself.
%  This is precisely why when searching graphs you must remember
%  where you have been in case you come round in a circle!
%