fig12_6.pl

来自「超多的prolog源代码 具体内容见压缩包里面的programs.txt」· PL 代码 · 共 48 行

% Figure 12.6  Problem-specific procedures for the eight 
% puzzle, to be used in best-first search of Figure 12.3.


/* Problem-specific procedures for the eight puzzle

Current situation is represented as a list of positions of the tiles, 
with first item in the list corresponding to the empty square.

Example:

                           This position is represented by:
3        1    2    3
2        8         4       [2/2, 1/3, 2/3, 3/3, 3/2, 3/1, 2/1, 1/1, 1/2]
1        7    6    5
          
         1    2    3

"Empty' can move to any of its neighbours which means 
that "empty' and its neighbour interchange their positions.
*/

% s( Node, SuccessorNode, Cost)

s( [Empty | Tiles], [Tile | Tiles1], 1)  :-  % All arc costs are 1
  swap( Empty, Tile, Tiles, Tiles1).         % Swap Empty and Tile in Tiles 

swap( Empty, Tile, [Tile | Ts], [Empty | Ts] )  :-
  mandist( Empty, Tile, 1).                  % Manhattan distance = 1

swap( Empty, Tile, [T1 | Ts], [T1 | Ts1] )  :-
  swap( Empty, Tile, Ts, Ts1).

mandist( X/Y, X1/Y1, D)  :-          % D is Manhhattan dist. between two squares
  dif( X, X1, Dx),
  dif( Y, Y1, Dy),
  D is Dx + Dy.

dif( A, B, D)  :-              % D is |A-B|
  D is A-B, D >= 0, !
  ;
  D is B-A.

% Heuristic estimate h is the sum of distances of each tile
% from its "home' square plus 3 times "sequence' score

h( [Empty | Tiles], H)  :-
  goal( [Empty1 | GoalSquares] ),