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).