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

问题描述

我在 prolog 中构建了一个代码来查找一系列合法的动作，其中马在棋盘的每个方格 (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.

我使用了如下逻辑:有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

右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 Knight's tour 谜题 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屋！