/**************************************************************** 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).