/*
	Prolog the Knight - A simple pathfinding program.

	Author: Dario D'Amico
	Date: 26 June 2011
*/

/*
	Entry point.
*/
:- initialization(main).

main :-
	knight(1, 1, 1, 4, 9, [], NewVisited),
	write('Path: '), write(NewVisited), nl.

/*
	Dungeon definition.
*/
floor(1, 1). floor(2, 1). floor(3, 1).
                          floor(3, 2). floor(4, 2). floor(5, 2).
floor(1, 3). floor(2, 3). floor(3, 3).              floor(5, 3).
floor(1, 4).                                        floor(5, 4).
floor(1, 5). floor(2, 5).              floor(4, 5). floor(5, 5).
             floor(2, 6). floor(3, 6). floor(4, 6).
                          floor(3, 7).
                          floor(3, 8).
                          floor(3, 9). floor(4, 9).

/*
	List manipulation.
*/
member(X, [X|R]).
member(X, [Y|R]) :- member(X,R).

append([X|Y], Z, [X|W]) :- append(Y, Z, W).
append([], X, X).

/*
	Arrived to destination.
*/
knight(X, Y, T, Xdst, Ydst, Visited, NewVisited) :-
	X = Xdst,
	Y = Ydst,
	not member(p(X, Y), Visited),
	append(Visited, [p(X, Y)], NewVisited).

/*
	The knight is on his way.
*/
knight(X, Y, T, Xdst, Ydst, Visited, NewVisited) :-
	(X \= Xdst ; Y \= Ydst),
	not member(p(X, Y), Visited),
	append(Visited, [p(X, Y)], NextVisited),
	floor(X, Y),
	member(d(Dx, Dy), [d(-1, 0), d(+1, 0), d(0, -1), d(0, +1)]),
	Xnext is X + Dx,
	Ynext is Y + Dy,
	Tnext is T + 1,
	knight(Xnext, Ynext, Tnext, Xdst, Ydst, NextVisited, NewVisited).