This code requires the Hamiltonian Cycle package.
/* tour(A, B, M, N, Tour) is true if Tour is a solution to the generalized */ /* knight's tour problem, where a knight can move to the opposite corner */ /* of an A x B rectangle on an M x N board. It is required that A =< B and */ /* M =< N. */ /* Due to the heuristics used, for some valid configurations it may be */ /* necessary to perform several runs in order to obtain a solution. And */ /* perhaps for some valid configurations, a solution will never be */ /* obtained. */ /* e.g. tour(1,2,5,6,Tour) could give Tour=[10,23,12,4,8,19,27,16,5,18,29, */ /* 21,25,14,1,9,20,7,3,11,24,28,15,2,13,26,22,30,17,6] */ tour(A, B, _, _, _):- A > 1, B mod A =:= 0, fail. tour(A, B, M, _, _):- A + B < M, M < 3 * A, fail. tour(A, B, M, N, Tour):- A > 0, A =< B, M > 0, M =< N, (A + B) mod 2 =:= 1, (M * N) mod 2 =:= 0, N >= A + B, generalized_knights(A, B, M, N, Graph), ham_cyc(Graph, Tour). /* generalized_knights(A, B, M, N, Graph) is true if Graph is a graph of all */ /* knight moves to the opposite corner of an A x B rectangle on an M x N */ /* board. */ generalized_knights(A, B, M, N, Graph):- MN is M * N, generalized_knights_1(MN, A, B, M, N, Graph). generalized_knights_1(0, _, _, _, _, []):-!. generalized_knights_1(V, A, B, M, N, [g(V,Ns)|Graph]):- V1 is V - 1, findall(W, move(V, A, B, M, N, W), Ns0), shuffle(Ns0, Ns), generalized_knights_1(V1, A, B, M, N, Graph). move(V, A, B, M, N, W):- I is (V-1) // N, J is (V-1) mod N, move_1(I, J, A, B, K, L), K >= 0, K < M, L >= 0, L < N, W is K * N + L + 1. move_1(I, J, A, B, K, L):- K is I - A, L is J - B ; K is I + A, L is J - B ; K is I - B, L is J - A ; K is I + B, L is J - A ; K is I - B, L is J + A ; K is I + B, L is J + A ; K is I - A, L is J + B ; K is I + A, L is J + B. /* shuffle(Xs, Ys) is true if Ys is a pseudo-random permutation of the set */ /* of elements in the list Xs. */ shuffle(Xs, Ys):- length(Xs, M), shuffle_1(Xs, M, Ys). shuffle_1([], 0, []):-!. shuffle_1(Xs, M, [X|Ys]):- N is int(rand(M)), nth_remove(Xs, N, X, Xs1), !, M1 is M - 1, shuffle_1(Xs1, M1, Ys). /* nth_remove(Xs, N, X, Ys) is true if X is the N-th (base 0) element of */ /* the list Xs, the remaining elements being Ys. This can be used to */ /* extract the N-th element [e.g. nth_remove([2,4,6,8],2,X,Ys)] or to */ /* insert an element at the N-th position [e.g. nth_remove(Xs,2,5, */ /* [2,4,6,8])]. When used to extract an element, on backtracking it */ /* will return all solutions [e.g. nth_remove([2,4,6,8],N,X,Ys)]. */ nth_remove(Xs, N, X, Ys):-nth_remove_1(Xs, X, 0, N, Ys). nth_remove_1([X|Ys], X, N, N, Ys). nth_remove_1([Y|Xs], X, N0, N, [Y|Ys]):- N1 is N0 + 1, nth_remove_1(Xs, X, N1, N, Ys).