使用 Warnsdorff 规则的 Knight' tour 主要给出了奇数大小的错误输出

Question

我写了一个代码来解决knight's tour problem，问题是有时会得到错误的输出。

特别是，非常频繁地使用奇数尺寸的棋盘：例如从位置 [0,1] 开始并使用 5X5 的棋盘它给我：

[[0, 1], [2, 0], [4, 1], [3, 3], [1, 4], [0, 2], [1, 0], [3, 1], [4, 3], [2, 2], [0, 3], [2, 4], [1, 2], [0, 0], [2, 1], [4, 0], [3, 2], [1, 3], [3, 4], [4, 2], [3, 0], [1, 1], [2, 3], [2, 3], [4, 4]]

如您所见，[2,3] 有重复。我检查了我的算法在给定电路板尺寸的情况下得到了多少错误输出，我发现奇数尺寸只有 50% 的时间正确输出，而偶数尺寸大约有 99% 的时间输出正确。怎么可能？

def rule(start , size):
    moves = [start ,]
    plus = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
    while 1 == 1 :
        d = 7
        for x in plus:
            s = list(plus)
            c = 0
            q = [ start[0]+x[0] , start[1]+x[1] ]
            if valid(q , size , moves):
                    if len(moves) == size ** 2 -1 :
                        moves.append(q)
                        return moves
                    s.remove((-x[0] , -x[1]))
                    for y in s :
                        p = [ q[0]+y[0] , q[1]+y[1] ]
                        if valid(p , size , moves):
                            c = c+1
                    if 0 < c <= d :
                        l = q
                        d = c
        start = l
        moves.append(start)
        
def valid(q , size , moves):
    if 0 <= q[0] < size  and 0 <= q[1] < size :
        if q not in moves:
            return True
    return False

Answer 1

当所选路径遇到 "dead end" 时会发生这种情况。

在您提到的示例中，起点为 [0,1]，大小为 5x5，这发生在选择方块 [2, 3] 时（第一次）。那时只需要再访问 2 个方块。它们是 [0,4] 和 [4,4]。但是这两个方块都没有未访问过的邻居。

因此，对于这两个有效的 q 移动，c 仍然为 0。这意味着 l 的值将 而不是 被设置——它保持其先前的值，仍然是 [2, 3]。因此，当您执行 start = l

时会添加此副本

Warnsdorff 规则并不能绝对保证实现巡回赛。在算法过程中的几个点上，存在平局——具有相等 c 值的移动。在这种情况下，您将使用具有此 c 值的最后一个。但可能你需要从这些关系中选择另一个关系才能获得成功。

所以要么你必须实施一个回溯算法，检测这样的 "dead ends" 并回溯到有平局的地方，然后从那里走另一条路。

或者您应该做一些更复杂的事情，因为似乎有一些方法可以从平局中选择 "right" 一步。请参阅 Wikipedia 以参考两篇描述成功打破平局方法的文章。

使用 Warnsdorff 规则的 Knight' tour 主要给出了奇数大小的错误输出

Knight' tour using Warnsdorff's rule gives wrong output with odd sizes mostly

python

python-3.x

algorithm

knights-tour