奈特旅游有效解

Question

我已经在prolog中构建了一个代码，以找到一系列合法的动作，其中骑士在棋盘(8x8)的每个方格上准确地着陆了一次。

我使用了如下的逻辑:有8种类型的骑士动作：

• 右1倒2
• 左1倒2
• 右2倒1
• 左2倒1
• 右1向上2
• 左1向上2
• 右2向上1
• 左2上1

右1，下移2：

 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.

对于所有8种类型的移动，都会重复这种情况。

问题是我的代码效率不高，要找到正确的路径需要花费太多的步骤。有谁知道解决这个问题的有效方法吗？

Answer 1

要想在可行的时间内解决8x8骑士的旅游难题，沃恩斯多夫法则可能是必须的。

我在中创建了一个程序，它很快地解决了这个难题。如果你需要程序在其他的Prolog中--翻译它或者仅仅使用它的一些想法并不是太困难。

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

Answer 2

这里有一个答案集编程(ASP)解决方案。它可以用于在可接受的时间内找到24x24的第一个解决方案，并且可以很容易地适应8x8的情况。它也使用Warnsdorff的规则，但比反向链接解决方案要快一些：

反向链接：

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

前向链接(使用ASP选择)：

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

前向链接代码更快，因为它使用前向存储来检查移动是否已经完成。这比在此检查中使用成员谓词更快。答案集编程代码如下：

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

代码使用来自Jekejeke的新模块"asp“。带有谓词knight_move/2和验证/1的完整代码位于gist 这里上。在那里，您还可以找到反向链接代码，这样您就可以并行地比较代码。