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

% EXAMPLES %

%> hanoi_ext(move(From,To),[[1,2],[],[]],State).

%

%> hanoi_ext(M1,[[1,2],[],[]],Mid), hanoi_ext(M2,Mid,State).

%