home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / prolog / 1569 < prev    next >
Encoding:
Internet Message Format  |  1992-08-20  |  3.9 KB
  1. Path: sparky!uunet!mcsun!uknet!edcastle!aiai!ken
  2. From: ken@aiai.ed.ac.uk (Ken Johnson)
  3. Newsgroups: comp.lang.prolog
  4. Subject: A little block stacking program
  5. Message-ID: <7254@skye.ed.ac.uk>
  6. Date: 20 Aug 92 17:50:09 GMT
  7. Followup-To: comp.lang.prolog
  8. Organization: Bugs-R-Us
  9. Lines: 129
  10.  
  11.  
  12.  
  13. % A little block stacking program.
  14. % Ken Johnson 20 August 1992
  15. % You may use and distribute this code freely but if you sell copies of it
  16. % at a profit, I want a share. 
  17. % 
  18. % The state of the game is represented in a canonical form; it is
  19. % important that your start and goal states are stated in canonical form. 
  20. % There is no check that the problem is correctly stated and feasible, so
  21. % don't say I didn't warn you.
  22. %
  23. % The canonical form is a term state/1 whose argument is list of lists of
  24. % atoms.  Each sublist is a pile, each atom is a brick name, leftmost on
  25. % top.  The empty pile does not exist.  Lists are ordered by their first
  26. % atom using sort/2.  So both
  27. % 
  28. %   A                    A
  29. %   B   C       and  C   B
  30. %   -----            -----
  31. % 
  32. % are represented as state([[a,b],[c]]) because a precedes c
  33. % 
  34. % The method uses iterative deepening and depth first search; this
  35. % combination is guaranteed to find first the path with the fewest moves. 
  36. % The part is a list of states.
  37.  
  38. % Run example_1/0 and example_2/0 to get the idea
  39.  
  40. % Example 1 starts from
  41. %                              C
  42. %   A                          B
  43. %   B  C      and moves to     A
  44.  
  45. example_1 :-
  46.     Start = state([[a,b],[c]]),
  47.     Goal  = state([[c,b,a]]),
  48.     search(Start,Goal,Path),
  49.     write('Start '), write(Start), nl,
  50.     write('Goal '), write(Goal), nl,
  51.     write('Path '), write(Path), nl.
  52.  
  53. % Example 2
  54. %                           B
  55. %   A                       C
  56. %   B   D                   D
  57. %   C   E               E   A
  58.  
  59. example_2 :-
  60.     Start = state([[a,b,c],[d,e]]),
  61.     Goal  = state([[b,c,d,a],[e]]),        % Canonical order!
  62.     search(Start,Goal,Path),
  63.     write('Start '), write(Start), nl,
  64.     write('Goal '), write(Goal), nl,
  65.     write('Path '), write(Path), nl.
  66.  
  67. % To search for a state
  68.  
  69. search(A,B,P) :-
  70.     search_w_lim(0,A,B,R),            % Iterative limit init 0
  71.     reverse(R,P).                % Reverse path as it is
  72.                                                 % saved in reverse order
  73. search_w_lim(N,A,B,R) :-
  74.     search(N,A,B,R).
  75.  
  76. search_w_lim(N,A,B,R) :-
  77.     N1 is N + 1,
  78.     search_w_lim(N1,A,B,R).
  79.  
  80. search(N,A,B,R) :-                % Real work starts here
  81.     search_1(N,[A],B,R).
  82.  
  83. search_1(_,[G|As],G,[G|As]).            % Found goal, succeed
  84.  
  85. search_1(N,[A|As],G,R) :-            % Not there yet
  86.     N > 0,                    % Can make more moves?
  87.     move(A,B),                % Find applicable move
  88.     \+ member(B,[A|As]),            % Check new state not used
  89.     N1 is N - 1,                % Decr move limit
  90.     search_1(N1,[B,A|As],G,R).        % Keep going
  91.  
  92. % What the moves are:
  93. % (a) Pick up a block of a pile of two or more blocks and put it
  94. %     on the table
  95.  
  96. move(state(Piles),state(Canonical)) :-
  97.     member([Block,Block_1|Pile],Piles,Piles_1),
  98.     sort([[Block],[Block_1|Pile]|Piles_1],Canonical).
  99.  
  100. % (b) Pick a block up off the table and put it onto a pile of one
  101. %     or more
  102.  
  103. move(state(Piles),state(Canonical)) :-
  104.     member([Block],Piles,Piles_1),
  105.     member(Pile,Piles_1,Piles_left),
  106.     sort([[Block|Pile]|Piles_left],Canonical).
  107.  
  108. % (c) Pick a block up off one pile of two or more and put it onto
  109. %     another pile of one or more.
  110.  
  111. move(state(Piles),state(Canonical)) :-
  112.     member([Block,B1|Bm],Piles,Piles_1),
  113.     member([A1|Am],Piles_1,Piles_2),
  114.     sort([[B1|Bm],[Block,A1|Am]|Piles_2],Canonical).
  115.  
  116. % Utilities
  117.  
  118. member(X,[X|_]).
  119. member(X,[_|T]) :-
  120.     member(X,T).
  121.  
  122. member(X,[X|R],R).
  123. member(X,[H|T],[H|R]) :-
  124.     member(X,T,R).
  125.     
  126.  
  127. reverse(A,B) :-
  128.     reverse(A,[],B).
  129.  
  130. reverse([],X,X).
  131.  
  132. reverse([H|T],Acc,Rev) :-
  133.     reverse(T,[H|Acc],Rev).
  134.  
  135. -- 
  136. ////  Advice to dieters:          ////  Ken Johnson, A I Applications Institute
  137. ////    Never eat more than       ////       80 South Bridge, EDINBURGH EH1 1HN
  138. ////    you can carry.            ////                 E-mail ken@aiai.ed.ac.uk
  139. ////               -- Miss Piggy  ////     phone 031-650 2756  fax 031-650 6513
  140.