4

我在序言中构建了一个代码，以找到一系列合法的动作，其中骑士恰好落在棋盘的每个方格（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 种类型的动作都重复

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

4

2 回答 2

6

为了能够在可行的时间内解决 8x8 Knight 的巡回赛难题，Warnsdorff 的规则可能是必须的。

我在 B-Prolog 中创建了一个程序，它可以很快地解决这个难题。如果您需要将程序放在其他 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
于 2014-01-11T23:02:03.357 回答
-1

这是一个答案集编程 (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 Prolog的新模块“asp” 。带有谓词 knight_move/2 和 verify/1 的完整代码在这里。还可以找到反向链接代码，以便可以并排比较代码。

于 2018-10-28T19:48:53.800 回答