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