优化单人数学解谜游戏求解性能的技术咨询

游戏背景与规则 #

这是一款单人解谜游戏，规则如下：

• 绘制10×10的方格区域
• 任选一个方格放置数字1（通常选(0,0)位置）
• 按特定跳跃规则从1数到100，在跳跃到达的方格填入对应数字
• 跳跃规则：水平/垂直方向跳过2个方格（一次移动3格）；对角线方向跳过1个方格（一次移动2格，坐标变化为±2,±2）

游戏示例：

问题描述 #

我用Python写了暴力搜索代码，但运行速度极慢——要探索的可能性达100!量级，完全不现实。我用的是11代i7处理器，但代码仅单核心运行，想请教如何提升速度或改进算法。

现有代码 #

class Gametable:

    def __init__( self ):
        #This value contains the maximum number reched by the algorithm
        self.max_reached = 1

    def start_at( self, coordX,  coordY ):
        tmpTable = [
            [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
            [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
            [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
            [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
            [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
            [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
            [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
            [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
            [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
            [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
        ]
        #We do not need to check the first jump, since the table should be empty.
        if self.is_valid_move( coordX, coordY, 1, tmpTable ):
            print("Found a solution!")
        else:
            print("Found no solution :(")

    def print_table( self, table ):
        print(52*"-")
        for X in range(10):
            for Y in range(10):
                if table[ X ][ Y ] == 0:
                    print("|    ", end="")
                else:
                    print("| {:02d} ".format( table[ X ][ Y ]), end='')
            print(" |")
            print(52*"-")
        print()


    def is_valid_move( self,  X,  Y,  counter,  table):

        # Check bounds
        if  X < 0:
            return False
        elif  X > 9:
            return False
        elif  Y < 0:
            return False
        elif  Y > 9:
            return False

        # Now check next steps
        if  table[ X ][ Y ]==0:
                table[ X ][ Y ] = counter
                if self.is_valid_move( X + 3, Y, counter+1, table ) or self.is_valid_move( X - 3, Y, counter+1, table ) or self.is_valid_move( X , Y + 3, counter+1, table ) or self.is_valid_move( X,  Y - 3, counter+1, table ) or self.is_valid_move( X + 2, Y + 2, counter+1, table ) or self.is_valid_move( X + 2, Y - 2, counter+1, table ) or self.is_valid_move( X - 2, Y + 2, counter+1, table ) or self.is_valid_move( X - 2, Y - 2, counter+1, table ):
                    return True
                else:
                    if counter > self.max_reached:
                        print("Max reached "+str(self.max_reached))
                        self.print_table(table)
                        self.max_reached = counter
                    table[X][Y] = 0 # We'll have to delete the last step if there is no further possibility
                    return False

mytable = Gametable()
mytable.start_at( 0, 0 )

优化方案 #

1. 用Warnsdorff启发式搜索替代暴力遍历 #

这是解决这类路径覆盖问题的核心优化——每次优先选择后续可移动选项最少的位置，而非盲目尝试所有方向。这种策略能快速剪掉大量死胡同路径，搜索效率提升几个数量级。

实现时，不要按固定顺序尝试8个方向，先计算每个合法下一跳位置的可移动次数，按次数升序排序后再递归尝试。

2. 奇偶性剪枝，提前排除无解路径 #

分析跳跃规则的奇偶性变化：

• 水平/垂直跳3格：坐标x或y的奇偶性翻转（比如x从偶变奇）
• 对角线跳2格：x和y的奇偶性都不变
  初始位置(0,0)是偶偶格，10×10方格中偶偶、奇偶、偶奇、奇奇格各25个。如果后续路径的奇偶性变化无法覆盖所有类型的格子，直接终止当前分支，无需继续搜索。

3. 多进程并行搜索 #

利用11代i7的多核心优势，把初始的几个分支拆分到不同进程同时运行。比如先找出数字1之后的所有合法位置，每个位置启动一个独立的搜索任务，用Python的multiprocessing模块实现。注意每个进程要维护独立的棋盘状态，避免共享数据冲突。

4. 数据结构提速 #

• 把二维棋盘换成一维数组（比如table[x*10 + y]），访问速度更快；
• 用位掩码记录已访问格子：100位刚好可以用Python大整数存储，判断格子是否被占用只需位运算(mask & (1 << pos)) == 0，比列表索引高效得多。

5. 预计算合法移动方向 #

提前遍历所有格子，预生成每个位置的合法下一跳坐标列表并存入字典。这样每次递归时不用重复判断边界，直接从字典取可用方向。

实操建议 #

先优先实现Warnsdorff法则，这是见效最快的优化。如果用启发式搜索后仍找不到解，再结合奇偶性分析判断是否存在解的可能——比如如果路径的奇偶性无法覆盖所有25个奇奇格，可直接判定无解。

内容的提问来源于stack exchange，提问作者LinuxCNC Nerd