Eight-Puzzle

The goal go(N, Moves), where N is between 1 and 30, will solve the Nth game included in the code. (A solution to the Nth game requires at least N moves.)

game( 1, p(1,2,6,
           4,3,8,
           5,7,0), p(1,2,6,
                     4,3,8,
                     5,0,7)).
game( 2, p(0,5,2,7,8,1,6,4,3), p(5,2,0,7,8,1,6,4,3)).
game( 3, p(2,6,5,3,8,7,1,0,4), p(0,6,5,2,3,7,1,8,4)).
game( 4, p(7,1,3,5,0,2,4,8,6), p(7,1,3,4,0,2,8,5,6)).
game( 5, p(1,4,6,8,3,0,5,7,2), p(8,1,6,5,4,3,0,7,2)).
game( 6, p(2,0,6,3,5,8,4,1,7), p(2,5,6,1,8,0,3,4,7)).
game( 7, p(2,3,7,0,1,8,4,6,5), p(2,7,8,1,6,3,4,5,0)).
game( 8, p(5,8,6,2,7,3,4,0,1), p(5,6,3,0,7,8,2,4,1)).
game( 9, p(3,5,6,1,2,8,4,7,0), p(1,3,5,8,2,6,4,0,7)).
game(10, p(5,1,2,8,6,7,3,4,0), p(1,2,0,5,3,7,6,8,4)).
game(11, p(4,3,6,0,2,5,1,7,8), p(4,3,5,1,0,2,7,6,8)).
game(12, p(2,1,3,7,0,6,5,8,4), p(1,6,8,7,2,3,0,5,4)).
game(13, p(1,0,6,3,5,8,2,4,7), p(1,5,7,3,8,4,2,6,0)).
game(14, p(4,2,3,6,0,5,7,8,1), p(0,5,8,4,3,2,6,7,1)).
game(15, p(6,3,8,0,2,5,1,7,4), p(1,2,0,5,8,6,7,3,4)).
game(16, p(5,3,6,2,1,4,0,7,8), p(3,1,6,7,5,4,8,2,0)).
game(17, p(1,0,6,8,3,2,5,7,4), p(8,1,7,2,5,6,0,3,4)).
game(18, p(3,4,7,1,0,5,2,8,6), p(4,7,2,5,1,6,3,8,0)).
game(19, p(4,1,7,8,3,0,5,6,2), p(0,7,2,4,8,1,3,6,5)).
game(20, p(7,8,3,2,0,5,4,1,6), p(6,5,7,8,2,3,0,4,1)).
game(21, p(5,0,1,8,4,2,3,7,6), p(3,8,4,6,1,2,0,7,5)).
game(22, p(1,2,0,7,4,5,3,6,8), p(6,3,4,7,0,1,8,2,5)).
game(23, p(8,5,2,0,6,7,4,1,3), p(1,6,0,7,5,2,3,8,4)).
game(24, p(5,1,0,6,8,2,7,4,3), p(3,1,5,4,0,7,6,2,8)).
game(25, p(2,8,3,0,1,5,4,7,6), p(6,3,4,1,2,7,0,5,8)).
game(26, p(1,7,5,4,0,3,2,8,6), p(0,7,2,5,8,6,4,3,1)).
game(27, p(6,1,2,5,8,0,4,7,3), p(0,4,8,1,7,3,2,5,6)).
game(28, p(2,4,6,7,0,5,3,1,8), p(1,8,3,4,5,7,0,6,2)).
game(29, p(2,0,1,6,8,4,3,7,5), p(0,5,7,3,8,4,1,6,2)).
game(30, p(0,2,6,8,3,7,5,1,4), p(4,2,5,1,3,8,6,7,0)).

move(p(0,B,C,D,E,F,G,H,I), B, p(B,0,C,D,E,F,G,H,I)).
move(p(0,B,C,D,E,F,G,H,I), D, p(D,B,C,0,E,F,G,H,I)).
move(p(A,0,C,D,E,F,G,H,I), A, p(0,A,C,D,E,F,G,H,I)).
move(p(A,0,C,D,E,F,G,H,I), C, p(A,C,0,D,E,F,G,H,I)).
move(p(A,0,C,D,E,F,G,H,I), E, p(A,E,C,D,0,F,G,H,I)).
move(p(A,B,0,D,E,F,G,H,I), B, p(A,0,B,D,E,F,G,H,I)).
move(p(A,B,0,D,E,F,G,H,I), F, p(A,B,F,D,E,0,G,H,I)).
move(p(A,B,C,0,E,F,G,H,I), A, p(0,B,C,A,E,F,G,H,I)).
move(p(A,B,C,0,E,F,G,H,I), E, p(A,B,C,E,0,F,G,H,I)).
move(p(A,B,C,0,E,F,G,H,I), G, p(A,B,C,G,E,F,0,H,I)).
move(p(A,B,C,D,0,F,G,H,I), B, p(A,0,C,D,B,F,G,H,I)).
move(p(A,B,C,D,0,F,G,H,I), D, p(A,B,C,0,D,F,G,H,I)).
move(p(A,B,C,D,0,F,G,H,I), F, p(A,B,C,D,F,0,G,H,I)).
move(p(A,B,C,D,0,F,G,H,I), H, p(A,B,C,D,H,F,G,0,I)).
move(p(A,B,C,D,E,0,G,H,I), C, p(A,B,0,D,E,C,G,H,I)).
move(p(A,B,C,D,E,0,G,H,I), E, p(A,B,C,D,0,E,G,H,I)).
move(p(A,B,C,D,E,0,G,H,I), I, p(A,B,C,D,E,I,G,H,0)).
move(p(A,B,C,D,E,F,0,H,I), D, p(A,B,C,0,E,F,D,H,I)).
move(p(A,B,C,D,E,F,0,H,I), H, p(A,B,C,D,E,F,H,0,I)).
move(p(A,B,C,D,E,F,G,0,I), E, p(A,B,C,D,0,F,G,E,I)).
move(p(A,B,C,D,E,F,G,0,I), G, p(A,B,C,D,E,F,0,G,I)).
move(p(A,B,C,D,E,F,G,0,I), I, p(A,B,C,D,E,F,G,I,0)).
move(p(A,B,C,D,E,F,G,H,0), F, p(A,B,C,D,E,0,G,H,F)).
move(p(A,B,C,D,E,F,G,H,0), H, p(A,B,C,D,E,F,G,0,H)).

/* iterative_deepening(Depth, Initial, Final, Moves) is true if Moves is a */
/*   sequence of moves to reach the Final position from the Initial        */
/*   position in at least Depth moves.                                     */
iterative_deepening(Depth, Initial, Final, Moves):-
  bounded_depth_first(Depth, Initial, Initial, Final, Moves).
iterative_deepening(Depth, Initial, Final, Moves):-
  iterative_deepening(s(Depth), Initial, Final, Moves).

/* bounded_depth_first(Depth, Current, Previous, Final, Moves) is true if  */
/*   Moves is a sequence of moves to reach the Final position from the     */
/*   Current position in exactly Depth moves.  Previous contains the       */
/*   previous position.                                                    */
bounded_depth_first(zero, Final, _, Final, []):-!.
bounded_depth_first(s(Depth), Current, Previous, Final, [Move|Moves]):-
  move(Current, Move, Next),
  Next \= Previous,
  bounded_depth_first(Depth, Next, Current, Final, Moves).

go(I, Moves):-
  game(I, InitialState, FinalState),
  iterative_deepening(zero, InitialState, FinalState, Moves), !.

The following procedure can be used to calculate the Manhattan distance of one position relative to another position.

/* manhattan(Initial, Final, Value) is true if Value is the sum of the     */
/*   Manhattan distances of each tile in the Initial position relative to  */
/*   the same tile in the Final position.  The value 0 denotes the empty   */
/*   cell.                                                                 */
/* e.g. manhattan([0,1,2,                                                  */
/*                 3,4,5,                                                  */
/*                 6,7,8], [8,7,6,                                         */
/*                          5,4,3,                                         */
/*                          2,1,0], 20).                                   */
manhattan(Initial, Final, Value):-
  manhattan_1(Initial, Final, 0, 0, Value). 
  
manhattan_1([], _, _, Value, Value).  
manhattan_1([0|Tiles], Final, N, Value0, Value):-
  !,
  N1 is N + 1,
  manhattan_1(Tiles, Final, N1, Value0, Value).
manhattan_1([Tile|Tiles], Final, N, Value0, Value):-
  Tile > 0,
  Row is N // 3, 
  Col is N mod 3,
  /* (Row, Col) is where the tile is. */
  destination(Final, Tile, 0, Row1, Col1),
  /* (Row1, Col1) is where the tile should be. */
  Value1 is Value0 + abs(Row1 - Row) + abs(Col1 - Col),
  N1 is N + 1,
  manhattan_1(Tiles, Final, N1, Value1, Value).
  
destination([Tile|_], Tile, N, Row, Col):-
  !,
  Row is N // 3, 
  Col is N mod 3.
destination([_|Tiles], Tile, N, Row, Col):-
  N1 is N + 1,
  destination(Tiles, Tile, N1, Row, Col).

The following procedure can be used to determine whether a given final position can be reached from a given initial position.

/* compatible(Initial, Final) is true if the Final position can be reached */
/*   from the Initial position.  The value 0 denotes the empty cell.       */
/* e.g. compatible([5,6,7,                                                 */
/*                  4,0,8,                                                 */
/*                  3,2,1], [1,2,3,                                        */
/*                           8,0,4,                                        */
/*                           7,6,5]).                                      */
compatible(Initial, Final):-
  length(Initial, Length),
  Side is sqrt(Length),
  manhattan0(Initial, Final, Side, Manhattan),
  parity(Initial, Final, Parity),
  compatible_1(Manhattan, Parity).

compatible_1(Manhattan, 1):-Manhattan mod 2 =:= 0, !.
compatible_1(Manhattan, -1):-Manhattan mod 2 =:= 1.

/* manhattan0(Initial, Final, Side, Value) is true if Value is the         */
/*   Manhattan distance of the hole in the Initial position relative to    */
/*   the hole in the Final position in a square of side Side.              */
manhattan0(Initial, Final, Side, Value):-
  manhattan0_1(Initial, Final, Side, 0, Value). 
  
manhattan0_1([0|_], Final, Side, N, Value):-
  !,
  Row is N // Side, 
  Col is N mod Side,
  /* (Row, Col) is where the hole is */
  destination0(Final, Side, 0, Row1, Col1),
  /* (Row1, Col1) is where the hole should be */
  Value is abs(Row1 - Row) + abs(Col1 - Col).
manhattan0_1([_|Tiles], Final, Side, N, Value):-
  N1 is N + 1,
  manhattan0_1(Tiles, Final, Side, N1, Value).
  
destination0([0|_], Side, N, Row, Col):-
  !,
  Row is N // Side, 
  Col is N mod Side.
destination0([_|Tiles], Side, N, Row, Col):-
  N1 is N + 1,
  destination0(Tiles, Side, N1, Row, Col).

/* parity(Xs, Ys, P) is true if P is the parity of the permutation Xs of   */
/*   Ys.  The value 1 represents an even parity; the value -1 an odd       */
/*   parity.                                                               */
parity(Xs, Ys, P):-
  permute(Xs, Ys),
  sign_of_product_of_differences(Xs, 1, D),
  sign_of_product_of_differences(Ys, 1, E),
  P is D * E.

sign_of_product_of_differences([], D, D).
sign_of_product_of_differences([Y|Xs], D0, D):-
  sign_of_product_of_differences_1(Xs, Y, D0, D1),
  sign_of_product_of_differences(Xs, D1, D).

sign_of_product_of_differences_1([], _, D, D).
sign_of_product_of_differences_1([X|Xs], Y, D0, D):-
  Y =\= X, /* Just in case Y = X ! */
  D1 is D0 * (Y - X) // abs(Y - X),  
  sign_of_product_of_differences_1(Xs, Y, D1, D).

/* permute(Xs, Ys) is true if Ys is a permutation of the list Xs.          */
permute([], []).
permute(Xs, [Y|Ys]):-
  remove(Y, Xs, Zs), permute(Zs, Ys). 

LPA Index     Home Page