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