 # hanext.p

```%  =================================================================
%  ==                                                             ==
%  ==          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            ==
%  ==                                                             ==
%  =================================================================```

### Code

```%  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],[],]
%  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],[],[]], [,,[]]  ).
hanoi_ext( move(2,1), [,,[]],  [[1,2],[],[]] ).

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

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

%  bottom left triangle from fig 3.5

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

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

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

%  bottom right triangle from fig 3.5

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

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

hanoi_ext( move(1,3), [,[],],  [[],[],[1,2]] ).
hanoi_ext( move(3,1), [[],[],[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), [[],,],  [,[],]  ).
hanoi_ext( move(1,2), [,[],],  [[],,]  ).

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

hanoi_ext( move(2,3), [,,[]],  [,[],]  ).
hanoi_ext( move(3,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

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

```

### Examples

```%  EXAMPLES
%
```
`%>  hanoi_ext(move(From,To),[[1,2],[],[]],State).`
```%
```
`%>  hanoi_ext(M1,[[1,2],[],[]],Mid), hanoi_ext(M2,Mid,State).`
```%

```