骑士之旅的高效解决方案 [英] knight's tour efficient solution

问题描述

我已经在序言中构建了代码，以查找一系列法律举动，其中骑士只一次落在棋盘的每个正方形上（8x8）。

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使用以下逻辑：
骑士移动有8种类型：

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

• 右1向下2


• 左1向下2


• 右2向下1


• 左2向下1


• 右1上2


• 左1上2


• 右2上1


• 左2上1

• 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

右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种移动方式都重复此操作

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?

推荐答案

能够解决8x8骑士的解谜游戏 Warnsdorff的规则可能是必须的时间。

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

我已经在B-Prolog中创建了一个程序，可以很快解决难题。如果您需要将该程序放在其他Prolog中-对其进行翻译不是很困难，或者只是使用其中的一些想法。

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

这篇关于骑士之旅的高效解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！