/****************************************************************
  LLP Example
	Knight's Tour (posed by Brook Taylor, 18C)
	Faster version
	by Naoyuki Tamura (tamura@kobe-u.ac.jp)
	   Dept. CS, Kobe University
****************************************************************/
/*
	Faster version
	(I, J) position is indexed by (N+2)*(I-1)+J-1
	because resource is hashed by its first argument

	Example output (N = 8)

	  1 12  9  6  3 14 17 20
	 10  7  2 13 18 21  4 15
	 31 28 11  8  5 16 19 22
	 64 25 32 29 36 23 48 45
	 33 30 27 24 49 46 37 58
	 26 63 52 35 40 57 44 47
	 53 34 61 50 55 42 59 38
	 62 51 54 41 60 39 56 43
*/


main :-
	write('Finds a Knight''s Tour (N>=8 takes a long time...)'), nl,
	write('N = '),
	readint(N),
	statistics(runtime, _),
	knight_tour(N),
	statistics(runtime, [_,T]),
	nl,
	write('CPU time = '), write(T), write(' msec'), nl.

knight_tour(N) :-
	n(N) =>
	(cont :- (solve(1,1) & write_board(N))) -<>
	place.

%
%  'place' creates resources
%  'k(K, _)' (K = (N+2)*(I-1)+J-1, I = 1..N, J = 1..N),
%  '!corner(K)' (K = (N+2)*(I-1)+J-1, I = 1,N, J = 1,N),
%  '!next_K(DK)' (DK = (N+2)*DI+DJ, (DI,DJ) = (+-2,+-1),(+-1,+-2))),
%  then calls 'cont'
%
place :-
	place(1, 1).

place(I, J) :-
	n(N),
	I > N,
	calc_K(1, 1, C1),
	calc_K(1, N, C2),
	calc_K(N, 1, C3),
	calc_K(N, N, C4),
	calc_DK(-2, -1, DK1),
	calc_DK(-2,  1, DK2),
	calc_DK(-1, -2, DK3),
	calc_DK(-1,  2, DK4),
	calc_DK( 1, -2, DK5),
	calc_DK( 1,  2, DK6),
	calc_DK( 2, -1, DK7),
	calc_DK( 2,  1, DK8),
	((corner(C1), corner(C2), corner(C3), corner(C4),
	  next_K(DK8), next_K(DK7), next_K(DK6), next_K(DK5),
	  next_K(DK4), next_K(DK3), next_K(DK2), next_K(DK1)) =>
	 cont).
place(I, J) :-
	n(N),
	J > N,
	I1 is I + 1,
	place(I1, 1).
place(I, J) :-
	n(N),
	I =< N, J =< N,
	calc_K(I, J, K),
	J1 is J + 1,
	(k(K, _) -<> place(I, J1)).

%
%  'solve(+I, +J)' finds knight tour starting from (I,J)
%
solve(I, J) :-
	n(N),
	Step = 1,
	calc_K(I, J, K),
	k(K, Step),
	solve(Step, N, K).

solve(Step, N, K) :-
	Step >= N*N.
solve(Step, N, K) :-
	Step < N*N,
	check(Step, N),
	Step1 is Step + 1,
	next(K, K1),
	k(K1, Step1),
	solve(Step1, N, K1).

check(Step, N) :-
	(Step mod  4 =:= 0, Step < N*N-1
	 -> \+ isolate_one(_)
	 ;  true),
%	(Step mod 20 =:= 0, Step < N*N-2
%	 -> \+ isolate_pair(_, _)
%	 ;  true),
	!.

isolate_one(K) :-
	k(K, _),
	no_neighbors(K).

isolate_pair(K1, K2) :-
	k(K1, _),
	next0(K1, K2),
	K1 < K2,
	k(K2, _),
	no_neighbors(K1),
	no_neighbors(K2).

no_neighbors(K) :- \+ (next0(K, K1), k(K1, _)).

% if current is a corner, it's ok
next(K, K1) :-
	corner(K),
	!,
	next0(K, K1).
% if the next can be a not-visitied corner, it should be selected
next(K, K1) :-
	next0(K, K1),
	corner(K1),
	not_visited(K1),
	!.
% otherwise
next(K, K1) :-
	next0(K, K1).

next0(K, K1) :- next_K(DK), K1 is K + DK.

not_visited(K) :-
	\+ \+ k(K, _).

calc_K(I, J, K) :-
	n(N),
	K is (N+2)*(I-1)+(J-1).

calc_DK(DI, DJ, DK) :-
	n(N),
	DK is (N+2)*DI+DJ.

%
%  'write_board(N)' writes step numbers S for each I = 1..N, J = 1..N
%  by consuming 'k(K, S)' (K = (N+2)*(I-1)+J-1)
%
write_board(N) :-
	for(I, 1, N),
	  nl,
	  for(J, 1, N),
	    calc_K(I, J, K),
	    k(K, Step),
	    write_number(Step),
	fail.
write_board(_) :-
	nl,
	top.

for(M, M, N) :- M =< N.
for(I, M, N) :- M =< N, M1 is M + 1, for(I, M1, N).

write_number(C) :- C < 10, !, write('  '), write(C).
write_number(C) :- write(' '), write(C).