:- module(_, [knights/2], [assertions, regtypes, nativeprops]).

:- entry knights(N, P) : num * term.
:- pred knights(N, P) : num * term.

knights(N, P) :-
	knights_(N, P).

:- pred knights_(N, P) : num * term => num * listpairnum.
knights_(N, P) :-
        path(N, 1, 1, P), !.

member_([X|_], X).
member_([_|Xs], X) :- member_(Xs, X).

:- pred path(S, X, Y, Path) : 
	num * num * num * term =>
	num * num * num * listpairnum.
path(S, X, Y, Path) :-
        S2 is S * S - 1,
        path_2(S2, [(X, Y)], S, Path).

:- pred path_2(Left, Path0, S, Path) : 
	num * listpairnum * num * term =>
	num * listpairnum * num * listpairnum.
path_2(0, Path, _, Path).
path_2(Left0, Path0, S, Path) :-
        Path0 = [P|_],
        P = (X, Y),
        move(X, Y, X1, Y1),
        valid(X1, Y1, S),
        New = (X1, Y1),
        \+ member_(Path0, New),
        Left is Left0 - 1,
        path_2(Left, [New|Path0], S, Path).

:- pred valid(X, Y, S) : num * num * num => num * num * num.
valid(X, Y, S) :-
        bound(X, S),
        bound(Y, S).

bound(X, S) :- X >= 1, X =< S.

:- pred move(X, Y, X1, Y1) : num * num * term * term => num * num * num * num.
move(X, Y, X1, Y1) :-
        delta(A, B),
        move_1(X, X1, A),
        move_1(Y, Y1, B).

delta(1, 2).
delta(2, 1).

:- pred move_1(X, X1, A) : num * term * num => num * num * num.
move_1(X, X1, A) :- X1 is X + A.
move_1(X, X1, A) :- X1 is X - A.

:- regtype listpairnum/1.
listpairnum([]).
listpairnum([X|Xs]) :- pairnum(X), listpairnum(Xs).

:- regtype pairnum/1.
pairnum((A,B)) :- num(A), num(B).
