knight's tour efficient solution

问题:

I have build a code in prolog to find a series of legal moves in which the knight lands on each square of the chessboard(8x8) exactly once.

I have used a logic like below: There 8 types of knight moves:

• right 1 down 2
• left 1 down 2
• right 2 down 1
• left 2 down 1
• right 1 up 2
• left 1 up 2
• right 2 up 1
• left 2 up 1

right 1 down 2 moves:

 move(X,Y) :- 
    C_X is X mod 8,      
        R_X is X // 8,       
        C_Y is C_X + 1,      % 1 right
        C_Y < 8,           
        R_Y is R_X + 2,      % 2 down
    R_Y < 8,
        Y is R_Y * 8 + C_Y,
    Y >= 0,
    X >= 0,
    X < 64,
    Y < 64.

And this is repeated for all 8 types of moves

The problem is that my code is not efficient, it takes too much steps to find the right path. Does anyone know an efficient way of solving this problem?

回答1:

To be able to solve 8x8 Knight's tour puzzle in a feasible amount of time Warnsdorff's rule is probably a must.

I've created a program in B-Prolog which solves the puzzle quite fast. If you need the program to be in some other Prolog - it's not too hard to translate it or just use some ideas from it.

knight_moves(X, Y, NewX, NewY) :-
    ( NewX is X - 1, NewY is Y - 2 
    ; NewX is X - 1, NewY is Y + 2 
    ; NewX is X + 1, NewY is Y - 2
    ; NewX is X + 1, NewY is Y + 2
    ; NewX is X - 2, NewY is Y - 1 
    ; NewX is X - 2, NewY is Y + 1 
    ; NewX is X + 2, NewY is Y - 1
    ; NewX is X + 2, NewY is Y + 1 ).

possible_knight_moves(R, C, X, Y, Visits, NewX, NewY) :-
    knight_moves(X, Y, NewX, NewY),
    NewX > 0, NewX =< R,
    NewY > 0, NewY =< C,
    \+ (NewX, NewY) in Visits.

possible_moves_count(R, C, X, Y, Visits, Count) :-
    findall(_, possible_knight_moves(R, C, X, Y, Visits, _NewX, _NewY), Moves),
    length(Moves, Count).

:- table warnsdorff(+,+,+,+,+,-,-,min).
warnsdorff(R, C, X, Y, Visits, NewX, NewY, Score) :-
    possible_knight_moves(R, C, X, Y, Visits, NewX, NewY),
    possible_moves_count(R, C, NewX, NewY, [(NewX, NewY) | Visits], Score).

knight(R, C, X, Y, Visits, Path) :-
    length(Visits, L),
    L =:= R * C - 1,
    NewVisits = [(X, Y) | Visits],
    reverse(NewVisits, Path).

knight(R, C, X, Y, Visits, Path) :-
    length(Visits, L),
    L < R * C - 1,
    warnsdorff(R, C, X, Y, Visits, NewX, NewY, _Score),
    NewVisits = [(X, Y) | Visits],
    knight(R, C, NewX, NewY, NewVisits, Path).


| ?- time(knight(8, 8, 1, 1, [], Path)).

CPU time 0.0 seconds.

Path = [(1,1),(2,3),(1,5),(2,7),(4,8),(6,7),(8,8),(7,6),(6,8),(8,7),(7,5),(8,3),(7,1),(5,2),(3,1),(1,2),(2,4),(1,6),(2,8),(3,6),(1,7),(3,8),(5,7),(7,8),(8,6),(7,4),(8,2),(6,1),(7,3),(8,1),(6,2),(4,1),(2,2),(1,4),(2,6),(1,8),(3,7),(5,8),(7,7),(8,5),(6,6),(4,7),(3,5),(5,6),(6,4),(4,3),(5,5),(6,3),(5,1),(7,2),(8,4),(6,5),(4,4),(3,2),(5,3),(4,5),(3,3),(2,1),(1,3),(2,5),(4,6),(3,4),(4,2),(5,4)]
yes

回答2:

Here is an answer set programming (ASP) solution. It can be used to find a first solution to a 24x24 in acceptable time and can be easily adapted to the 8x8 case. It uses Warnsdorff's rule as well, but is a little faster than a backward chaining solution:

Backward Chaining:

?- time(knight_tour((1,1), X)).
% Up 878 ms, GC 32 ms, Thread Cpu 859 ms (Current 10/30/18 20:55:28)
X = [(1,1),(3,2),(5,1),(7,2),(9,1),(11,2),(13,1),(15,2),(17,1), ...

Forward Chaining (With ASP Choice):

?- time(knight_tour((1,1), X)).
% Up 411 ms, GC 0 ms, Thread Cpu 406 ms (Current 10/28/18 20:45:05)
X = [(1,1),(3,2),(5,1),(7,2),(9,1),(11,2),(13,1),(15,2),(17,1), ...

The forward chaining code is faster, since it uses the forward store to check to see whether a move was already done or not. This is faster than using a member predicate for this check. The answer set programming code reads:

:- use_module(library(basic/lists)).
:- use_module(library(minimal/asp)).

knight_tour(Start, Solution) :-
   post(go(Start, 1)),
   findall(X, go(X,_), Solution).

choose(S) <= posted(go(X,N)), N \== 576,
   findall(W-Y, (move(X, Y), weight(Y, X, W)), L),
   keysort(L, R),
   M is N+1,
   strip_and_go(R, M, S).

strip_and_go([_-Y|L], M, [go(Y, M)|R]) :-
   strip_and_go(L, M, R).
strip_and_go([], _, []).

weight(X, Z, N) :-
   findall(Y, (move(X, Y), Z \== Y), L),
   length(L, N).

move(X, Y) :-
   knight_move(X, Y),
   verify(Y),
   \+ clause(go(Y, _), true).

The code uses the new module "asp" from Jekejeke Prolog. The full code with predicates knight_move/2 and verify/1 is on gist here. There one finds the backward chaining code as well so that one can compare the code side by side.