% File : /usr/lib/prolog/search/eight_puzzle
% Author : R.A.O'Keefe
% Updated: 12 December 1983
% Purpose: illustrate the searching methods
/* The illustration I have chosen is the well known 8-puzzle.
The state of the game is represented by a tuple of 9 labels,
1 to 8 representing the movable tiles and x representing an
empty square, together with an integer between 1 and 9 which
says where the empty square is. The operations are moving
the empty square u(p), d(own), l(left), or r(right).
*/
solution(5/b(
1,2,3,
8,x,4,
7,6,5) ).
starting_position(9/b(
1,2,3,
7,8,4,
6,5,x) ).
equivalent(X, X).
operator_applies(Operator, OldX/OldB, NewX/NewB) :-
operator_ok(Operator, OldX, NewX),
new_board(OldX, OldB, NewX, NewB).
operator_ok(u, OldX, NewX) :- OldX > 3, NewX is OldX-3.
operator_ok(d, OldX, NewX) :- OldX < 7, NewX is OldX+3.
operator_ok(l, OldX, NewX) :- OldX mod 3 =\= 1, NewX is OldX-1.
operator_ok(r, OldX, NewX) :- OldX mod 3 =\= 0, NewX is OldX+1.
% new_board(OldX, OldB, NewX, NewB)
% creates a New Board which is essentially the same as the Old Board,
% except that the labels at the Old and New X positions have been
% swapped.
new_board(OldX, OldB, NewX, NewB) :-
functor(OldB, F, N),
functor(NewB, F, N),
arg(OldX, OldB, x),
arg(NewX, OldB, L), % L is a label 1..8
arg(OldX, NewB, L),
arg(NewX, NewB, x),
new_board(N, OldB, NewB).
new_board(0, _, _) :- !.
new_board(N, OldB, NewB) :-
arg(N, NewB, Lab),
var(Lab),
!,
arg(N, OldB, Lab),
M is N-1,
new_board(M, OldB, NewB).
new_board(N, OldB, NewB) :-
M is N-1,
new_board(M, OldB, NewB).
distance(X1/Board1, Distance) :-
solution(X2/Board2),
distance(9, Board1, Board2, 0, Distance).
distance(0, _, _, Distance, Distance) :- !.
distance(N, Board1, Board2, SoFar, Distance) :-
arg(N, Board1, Piece),
arg(N, Board2, Piece),
!,
M is N-1,
distance(M, Board1, Board2, SoFar, Distance).
distance(N, Board1, Board2, SoFar, Distance) :-
M is N-1,
Accum is SoFar+1,
distance(M, Board1, Board2, Accum, Distance).