Generalized Knight's Tour

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

LPA Index     Home Page