% Bratko Figure 12.6. Problem-specific procedures for the eight puzzle
% to be used with the A-star best-first search of Bratko Figure 12.3.

/* Problem-specific procedures for the eight puzzle

Current state is represented as a list of positions of tiles in the form X/Y,
with the first item corresponding to the position of "empty" and the rest to
those of the tiles 1-8.

Example:

         State             Representation

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

Moves are handled by swapping the positions of "empty" and one of its neighbours.

*/

% 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]) :-	% Swap allowed if Manhattan = 1
	mandist(Empty, Tile, 1).

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

mandist(X/Y, X1/Y1, D) :-			% D is Manhhattan distance between two positions
	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, !.

dif(A, B, D) :-		% D is |A-B|
	D is B-A.

goal([2/2,1/3,2/3,3/3,3/2,3/1,2/1,1/1,1/2]).	% Goal positions for tiles

% Display a solution path as a list of board positions

showsol([]).

showsol([P|L]) :-
	showsol(L),
	nl, write('---'),
	showpos(P).

% Display a board position

showpos([S0,S1,S2,S3,S4,S5,S6,S7,S8]) :-
	member(Y, [3,2,1]), nl,				% Order to display Y-coordinates
	member(X, [1,2,3]),				% Order to display X-coordinates
	member(Tile-X/Y,				% Tile currently at position X/Y
	        [' '-S0,1-S1,2-S2,3-S3,4-S4,5-S5,6-S6,7-S7,8-S8]),
	write(Tile),
	fail						% Backtrack to next position
	;
	true.						% All positions displayed

% Start positions for some puzzles

start1([2/2,1/3,3/2,2/3,3/3,3/1,2/1,1/1,1/2]).	% Requires 4 steps

start2([2/1,1/2,1/3,3/3,3/2,3/1,2/2,1/1,2/3]).	% Requires 5 steps

start3([2/2,2/3,1/3,3/1,1/2,2/1,3/3,1/1,3/2]).	% Requires 18 steps

% Example query: ?- start1(Pos), solve(Pos, Sol), showsol(Sol).

% --------------------------------------------------------------------
% The rest is needed only for A*Search (To compute the heuristic)
% --------------------------------------------------------------------

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

h([Empty|Tiles], H) :-
	goal([Empty1|GoalPositions]),
	totdist(Tiles, GoalPositions, D),	% Total distance from home positions
	seq(Tiles, S),				% Sequence score
	H is D + 3*S.

totdist([], [], 0).

totdist([Tile|Tiles], [Position|Positions], D) :-
	mandist(Tile, Position, D1),
	totdist(Tiles, Positions, D2),
	D is D1 + D2.

% seq(TilePositions, Score): sequence score

seq([First|OtherTiles], S) :-
	seq([First|OtherTiles], First, S).

seq([Tile1, Tile2|Tiles], First, S) :-
	score(Tile1, Tile2, S1),
	seq([Tile2|Tiles], First, S2),
	S is S1 + S2.

seq([Last], First, S) :-
	score(Last, First, S).

score(2/2, _, 1) :- !.		% Tile in centre scores 1

score(1/3, 2/3, 0) :- !.	% Proper successor scores 0
score(2/3, 3/3, 0) :- !.
score(3/3, 3/2, 0) :- !.
score(3/2, 3/1, 0) :- !.
score(3/1, 2/1, 0) :- !.
score(2/1, 1/1, 0) :- !.
score(1/1, 1/2, 0) :- !.
score(1/2, 1/3, 0) :- !.

score(_, _, 2).			% Tiles out of sequence score 2