简介一份基于Java与Eclipse的谜题求解器项目面向正在学习Java Swing、MVC架构以及搜索回溯算法的读者适合作为计算机科学II课程项目参考或自学进阶练习。项目覆盖时钟步进、水壶问题和单人象棋三类经典谜题通过统一接口抽象不同求解问题并用模型-视图-控制器模式分离界面与业务逻辑结构清晰易于理解和二次扩展。压缩包共60个文件包含16个Java源文件、17个编译后class文件、10个文本棋盘与数据配置另有Eclipse工程文件、README说明和设计文档整体约51KB小巧完整。已有657人学习浏览可直接导入Eclipse运行借助内置多组棋盘输入观察不同规模的求解过程对掌握状态空间搜索、剪枝策略及GUI事件驱动编程均有实际帮助。完整源码配合详细设计文档能让读者同时获得项目组织思路与谜题建模方法是课程作业和算法实验的实用参考。代码注释清晰从接口定义到具体回溯实现都便于逐行研读适合作为中等难度算法项目的入门范本。1. PuzzleSolver 是什么把三类经典谜题收进同一套搜索框架之前遇到一道时钟步的谜题我按模运算写了个循环过了几天同事问我水壶问题我打开编辑器又写了一遍 BFS。等到周末玩单人象棋残局我意识到自己马上就要写出第三份几乎一模一样的 BFS 时PuzzleSolver 这个项目就在我脑子里冒出来了。它不是一个 fancy 的算法库就是一套把状态、动作、目标检测抽出来再共用搜索引擎的小框架。时钟步、水壶、单人象棋这三类问题实际上都能表示成状态空间上的最短路径搜索。这篇文章会从建模思路讲到具体实现再列出我踩过的几个坑最后补一个提速技巧。适合在学搜索算法、准备面试或者自己想做游戏谜题辅助工具的人。2. 从状态空间建模开始时钟步、水壶和单人象棋为何都适合用统一搜索解2.1 状态、动作和目标把谜题翻译成图上的搜索任何一个搜索类谜题都可以抽象成一个状态机。状态就是某一时刻的情形动作是从一个状态转移到另一个状态的合法操作目标检测是判断当前状态是否为解。把状态看成图上的节点动作看成边问题就变成了“从初始状态出发找一条到达目标状态的路径并且路径最短”。这个翻译过程不依赖具体谜题所以三个谜题能共用同一套搜索框架。这三类谜题的抽象方式如下时钟步状态是当前时刻0 到 M-1 的整数动作是选一个步长加到当前时刻上再取模目标是到达指定时刻。水壶状态是二元组一号壶水量二号壶水量动作是倒满、倒空、壶之间互倒目标是任一壶中水量等于目标量。单人象棋吃子规则变体状态是棋盘上所有棋子的位置集合动作是选择一子按规则走到一个被占据的位置并吃掉它目标是只剩一个棋子。这样统一后搜索引擎只需要两个接口get_neighbors(state)返回所有后继状态is_goal(state)判断是否到达目标。至于谜题内部怎么表示、怎么生成动作引擎完全不关心。2.2 BFS 为什么比 A* 和 DFS 更稳妥最优步数与状态规模BFS广度优先搜索按层扩展第一次遇到目标时就是最短步数这对“最少几步”类谜题是最直接的需求。DFS 虽然省内存但容易一头扎进很深的路径尤其当动作可逆时会无限循环就算维护 visited也可能先找到一个非常长的解最优性无法保证。A* 需要设计启发函数三个谜题要统一启发并不容易比如时钟步的启发可以设计成与目标的模差值水壶可以用到目标量最近的壶容量差单人象棋可以用剩余棋子数但启发设计不当时会导致次优解甚至搜索空间更大。做 PuzzleSolver 第一步用 BFS 是最稳妥的。BFS 的缺点是内存占用高所以去重和剪枝是必需品。下面表格列出了三个谜题在默认小参数下的状态规模可以看到 BFS 在多数常规实例下完全能扛住。谜题状态表示单步分支数典型状态数默认参数时钟步int (0..M-1)len(steps)M 个M 通常不超过 100水壶(int, int)最多 6(A1)*(B1)通常几千单人象棋位棋盘 int与棋子数和棋盘大小有关2^(格子数) 量级4x4 为 655362.3 状态去重和剪枝让搜索空间从天文数字降到可算没有去重BFS 会指数爆炸。去重的核心是维护一个 visited 集合每个状态必须转换成可哈希的 key。剪枝的常见做法有三种步数界、规则剪枝、对称剪枝。步数界是指如果当前步数已经达到已知可行解长度就不再扩展规则剪枝例如倒空一个本来空的壶没有意义直接跳过对称剪枝在单人象棋里特别有效棋盘旋转或翻转后状态等价可以只保留一个。PuzzleSolver 的通用 BFS 我会写成下面这样所有谜题共用这一个函数from collections import deque from typing import Callable, List, Any, Optional def bfs(start: Any, is_goal: Callable[[Any], bool], get_neighbors: Callable[[Any], List[Any]], state_key: Callable[[Any], Any] lambda x: x) - Optional[List[Any]]: 通用 BFS返回从 start 到目标的路径状态列表无解返回 None。 if is_goal(start): return [start] visited {state_key(start)} # 队列元素为 (当前状态, 到达该状态的路径) queue deque([(start, [start])]) while queue: state, path queue.popleft() for next_state in get_neighbors(state): key state_key(next_state) if key in visited: continue visited.add(key) new_path path [next_state] if is_goal(next_state): return new_path queue.append((next_state, new_path)) return None这里的逻辑很直白is_goal和get_neighbors由每个谜题自己提供state_key用于把不可哈希的状态转成 tuple 或字符串。队列中同时存路径是为了让返回结果直观如果只关心步数可以改成存父指针然后回溯但第一版用路径列表最容易验证正确性。start可以是任何类型get_neighbors必须返回不包含重复的后继列表同时保证每个后继都是新对象避免共享引用。设计一个可用的状态对象有三个要求可哈希、可比较、可复制。可哈希是为了进 visited可比较是为了判断两个状态是否相等可赋值是为了避免路径中多个状态引用同一个可变对象。只要满足这三条就能挂到这个通用引擎上。3. 时钟步与水壶求解两个小状态空间的实现与参数3.1 时钟步模数、步长列表与最短步数时钟步谜题的定义是有一个 M 格时钟起始时间是 start每次从步长列表 steps 中选一个数字把当前时间向前拨该数字可能超过一圈问最少几步能到达 target。比如 M12start3steps[4,7]target2那么 3 加 4 加 7 再取模后可能到达 2。问题本质是模线性组合但我们要的是最短步数所以用 BFS。建模时有两个容易出错的地方一是负步长二是重复步长。负步长在模运算里可以归一化到[0, M-1]例如-2 % 12 10表示倒拨两小时等价于正拨十小时。重复步长做完模后可能变成同一个数直接去重。零步长没有意义丢弃。另外如果所有步长与 M 的最大公约数为 g那么能访问到的状态必须和 start 模 g 同余如果 target 与 start 模 g 不同直接无解。这个预先判断能避免空跑 BFS。from collections import deque from math import gcd from functools import reduce def solve_clock(M: int, start: int, steps: list[int], target: int) - list[int] | None: 求解时钟步谜题返回从 start 到 target 的时间序列无解返回 None。 start % M target % M # 步长归一化 去重丢弃 0 step_set set() for s in steps: step_set.add(s % M) step_set.discard(0) if not step_set: return [start] if start target else None steps list(step_set) # 数论预判不可达直接返回 g reduce(gcd, steps [M]) if (target - start) % g ! 0: return None if start target: return [start] visited [False] * M parent [-1] * M action_at [None] * M q deque([start]) visited[start] True while q: cur q.popleft() for step in steps: nxt (cur step) % M if not visited[nxt]: visited[nxt] True parent[nxt] cur action_at[nxt] step if nxt target: # 回溯路径 path [] node target while node ! start: path.append(node) node parent[node] path.append(start) path.reverse() return path q.append(nxt) return None逻辑说明先做数据预处理再用 gcd 预判无解最后 BFS。这里用parent数组记录前驱回溯得到完整路径比在队列里存整条路径省内存。visited用布尔数组而不是 set因为状态是连续的整数下标访问更快。action_at在这个实现里没有直接用到但便于调试时确认每步用了哪个步长。参数说明M必须大于 0start、target会自动取模steps允许负数和大于 M 的数内部统一归一化。如果steps中的步长模 M 后相同只保留一个因为效果完全一样。g reduce(gcd, steps [M])这一步是关键它能把“无解但 BFS 空转”的情况提前拦截。返回的路径包含首尾状态长度减一就是步数。3.2 水壶六种动作与gcd判断水壶问题是经典面试题两个容量分别为 A 和 B 的水壶初始都为空允许倒满、倒空、互相倒问是否能在某个壶中刚好得到目标水量 C。状态表示就是(x, y)x 是一号壶当前水量y 是二号壶水量。动作生成六种后继倒满一号壶、倒满二号壶、倒空一号壶、倒空二号壶、一号倒入二号、二号倒入一号。目标判断是x C or y C。数论预判有两个条件C 必须能被gcd(A, B)整除且 C 不能超过两个壶容量的较大值。否则不可能实现。注意 C0 是特例初始状态就是解。from collections import deque from math import gcd def solve_water(A: int, B: int, C: int) - list[tuple[int, int]] | None: 求解两个水壶问题返回状态路径无解返回 None。 if C max(A, B): return None if C % gcd(A, B) ! 0: return None start (0, 0) if C 0: return [start] def get_neighbors(state): x, y state res [] # 倒满 if x A: res.append((A, y)) if y B: res.append((x, B)) # 倒空 if x 0: res.append((0, y)) if y 0: res.append((x, 0)) # 1-2倒入量取 x 和 B-y 的较小值 if x 0 and y B: t min(x, B - y) res.append((x - t, y t)) # 2-1 if y 0 and x A: t min(y, A - x) res.append((x t, y - t)) return res visited {start} q deque([(start, [start])]) while q: state, path q.popleft() for nxt in get_neighbors(state): if nxt in visited: continue visited.add(nxt) new_path path [nxt] if nxt[0] C or nxt[1] C: return new_path q.append((nxt, new_path)) return None逻辑说明get_neighbors严格生成六种操作每种操作前都判断是否真的改变了状态。比如倒满一号壶时先判断x A否则会产生自环导致 visited 重复。倒入动作的转移量计算是min(源壶当前水量, 目标壶剩余容量)这是倒水问题的标准写法。这里的路径直接存在队列中状态空间不大时可以接受如果 A 和 B 都是 1000 量级状态数达到百万建议改成和时钟步一样的 parent 回溯方案。参数说明A、B 建议大于 0。C 必须是非负整数。这个实现会把目标状态放在扩展后检查所以返回的路径中最后一个状态一定是目标状态。使用solve_water(3, 5, 4)会得到一条类似(0,0)-(5,0)-(2,3)的路径每一步都能对应一个物理操作方便人工校验。这里还要提醒一个常见误用有些水壶变体要求“两个壶的总水量等于 C”而不是“某个壶中水量等于 C”。两种建模的目标判断完全不同实现前必须确认题目定义。PuzzleSolver 中我用的是经典定义即某个壶中恰好为 C。4. 单人象棋求解一个“大状态空间”的搜索设计4.1 单人象棋吃子谜题规则定义与状态表示单人象棋有多种玩法PuzzleSolver 里的实现采用 Solitaire Chess 的吃子规则但为了控制复杂度只保留“马”这一种棋子。棋盘大小为 N x N默认 4x4初始放若干棋子。每次必须选择一个马按 L 形走法跳到一个已被另一个马占据的格子上吃掉它自己落在该格子。目标状态是棋盘上只剩一个马。这个规则已经能体现搜索的核心难点每一步必须吃子状态数量随棋盘增大而指数增长。状态表示用位棋盘bitboard最合适。一个 N x N 棋盘共N*N个格子用一个整数 bitmask 表示bit 为 1 说明该格有棋子。比如 4x4 棋盘格子按行优先编码第 0 到第 15 位分别对应(0,0)到(3,3)。这样状态就是一个整数可以非常高效地放入 visited 集合。动作生成前先预计算每个格子所有 L 形目标格子列表避免循环里反复计算坐标偏移。关键规则细节马移动目标格必须有棋子因为这是一道“吃子谜题”不允许走到空格。这个细节非常容易写错我把它放在第 5 章的避坑里详细讲。4.2 用 BFS 位棋盘实现求解器下面是一个朴素的 BFS 求解器适合 4x4 棋盘。from collections import deque def solve_solitaire(size: int, pieces: list[tuple[int, int]]) - list[int] | None: 求解单人象棋马吃子版返回位棋盘状态序列无解返回 None。 n_cells size * size def idx(pos): r, c pos return r * size c start 0 for p in pieces: start | (1 idx(p)) # 预计算每个格子的 L 形目标格子 moves [[] for _ in range(n_cells)] for r in range(size): for c in range(size): cell r * size c for dr, dc in [(1,2),(1,-2),(-1,2),(-1,-2), (2,1),(2,-1),(-2,1),(-2,-1)]: nr, nc r dr, c dc if 0 nr size and 0 nc size: moves[cell].append(nr * size nc) def neighbors(mask): res [] m mask while m: lowbit m -m i lowbit.bit_length() - 1 m - lowbit for j in moves[i]: if mask (1 j): # 目标必须有棋子 new_mask mask ~(1 i) res.append(new_mask) return list(set(res)) def is_goal(mask): # 只剩一个棋子bitmask 只有一个 bit 为 1 return mask ! 0 and (mask (mask - 1)) 0 if is_goal(start): return [start] visited {start} q deque([(start, [start])]) while q: cur_mask, path q.popleft() for nxt in neighbors(cur_mask): if nxt in visited: continue visited.add(nxt) new_path path [nxt] if is_goal(nxt): return new_path q.append((nxt, new_path)) return None逻辑说明neighbors里用lowbit循环提取 mask 中所有为 1 的位每个位代表一个棋子。对每个棋子找到它的所有 L 形目标格子目标格有棋子时才能执行吃子。new_mask mask ~(1 i)把原位置清 0因为目标位置 j 原本就是 1所以新状态天然包含 j不需要额外置位。最后一行list(set(res))是为了去掉重复状态因为同一个新位棋盘可能由不同棋子移动得到但状态相同无需重复扩展。参数说明pieces的坐标范围必须在 0 到 size-1 之间。size4时状态空间最多 65536普通 BFS 完全没问题size5时状态空间最多 3355 万BFS 会消耗几百兆内存不建议用这个朴素版本可以改用下一节的对称剪枝或第 6 章的双向 BFS。返回的是位棋盘状态序列不是坐标序列调试时可以用bin(path[-1])查看最终只剩哪一个棋子。4.3 对称性剪枝与排列去重状态数量再降一半以上位棋盘最实用的剪枝是棋盘对称性。一个 4x4 棋盘旋转 90 度、180 度、270 度或水平翻转、垂直翻转、沿对角线翻转谜题本质没有任何变化。因此可以在放入 visited 前把位棋盘所有对称变换中数值最小的那个作为 state_key。这样能去掉大量重复状态实际搜索时间可以减半以上。def rotate_board(mask, size): 顺时针旋转 90 度后返回新 bitmask。 new_mask 0 for r in range(size): for c in range(size): bit (mask (r * size c)) 1 if bit: nr, nc c, size - 1 - r new_mask | (1 (nr * size nc)) return new_mask def flip_board(mask, size): 水平翻转后返回新 bitmask。 new_mask 0 for r in range(size): for c in range(size): bit (mask (r * size c)) 1 if bit: new_mask | (1 (r * size (size - 1 - c))) return new_mask将旋转和翻转组合起来可以得到 8 种对称状态。使用方法是在通用 BFS 的state_key参数里传入一个make_symmetry_key函数它把 mask 经过 4 次旋转和每次旋转后的水平翻转共 8 个值取最小值作为 key。这样就不会把一个状态的不同对称形式当成不同状态反复扩展。需要说明的是对称剪枝只在棋盘本身具有对称性时才有效比如 4x4、5x5 都适用而奇数尺寸棋盘的对称中心会影响旋转效果但整体仍然是等价的。这个剪枝对棋子排列没有额外限制应用起来非常简单建议所有棋类搜索都加上。5. PuzzleSolver 避坑指南五个让我翻车的细节5.1 状态去重用可变 list 导致哈希报错现象刚实现水壶求解时visited 直接visited.add(state)而 state 是一个[x, y]列表运行立刻报TypeError: unhashable type: list。原因Python 的 list 是可变类型不能作为 set 或 dict 的 key。水壶状态用列表表示非常自然但 Python 不认账。解决把状态统一成 tuple或者在通用 BFS 的state_key参数里做转换例如lambda s: tuple(s) if isinstance(s, list) else s。我后来在 PuzzleSolver 的通用函数里默认加了这一层转换避免每个谜题自己处理。但要注意如果状态里嵌套 list比如棋盘是二维列表tuple 只转换了外层内层仍然不可哈希这时候需要自定义 key比如转成字符串或 frozenset。5.2 时钟步的负步长和取模语义现象测试用例里有steps[-2, 3]结果程序声称无解但手工推演两步就能到达目标。原因负步长在模运算里如果不归一化容易踩到不同语言取模语义的差异。Python 的(-2) % 12结果是 10这没问题但我在预处理时又加了手动修正修正逻辑写反了把原本正确的 10 又变回了 -2。解决在 BFS 之前把所有步长归一化到[0, M-1]用step % M统一处理。这样负步长自动变成等价的正步长BFS 内部所有运算都基于非负整数不会出现负数。同时如果步长模 M 后重复只保留一个既减少分支数又避免状态重复。5.3 水壶问题无解时 BFS 空转现象输入A6, B10, C5程序运行了很久才返回 None中间遍历了几百个状态。原因6 和 10 的最大公约数是 25 不是 2 的倍数所以无解。没有提前用 gcd 做数学判断BFS 会遍历完所有可达状态才确认无解。虽然有 visited 不会死循环但效率很低尤其在 A、B 较大时。解决在 BFS 前加两个预判条件C max(A, B)直接无解C % gcd(A, B) ! 0直接无解。注意 C0 是初始解不要被第一个条件拦截。这个 gcd 预判是水壶问题的标准数学结论放进 PuzzleSolver 后无解用例的返回值是瞬间的。5.4 单人象棋的“吃子”动作被误建成“走到空格”现象求解 4x4 单人象棋程序一两秒就返回一条路径但人工核对发现其中一步马走到了空格。原因我把动作生成了普通国际象棋马的走法只检查目标格在棋盘内没有检查目标格是否有棋子导致“不吃子移动”混进了动作集合。这不符合“每步必须吃子”的规则搜索到的自然不是合法解。解决在neighbors中增加严格判断if mask (1 j):目标格必须有棋子才能走。另外我让neighbors返回所有合法吃子后的新状态而不是同时混入普通移动。这件事提醒我写搜索前先把规则边界在黑板上写清楚再写代码否则搜索越快错误的解也越快。5.5 递归 DFS 超过 Python 默认递归深度现象用递归实现 DFS 求解单人象棋时偶尔报RecursionError: maximum recursion depth exceeded即使棋盘只有 5x5。原因默认递归深度虽然 1000但问题出在我没有维护路径去重DFS 在“吃子后又被吃回来”这类可逆动作上反复横跳路径长度远超预期。我还试过设置sys.setrecursionlimit(100000)结果坏输入直接把内存吃满得不偿失。解决不要盲目调高递归上限。改用显式栈的迭代 DFS或者直接用 BFS并且 visited 状态必须在进入下一层之前就标记不能等到弹出状态时再标记否则同一层内会有大量重复。PuzzleSolver 最后统一用 BFS 和迭代 DFS顺便解决了“递归层数不可控”这个玄学问题。6. 进阶技巧双向 BFS 和对称剪枝让求解快一个数量级时钟步和目标状态明确的水壶问题非常适合用双向 BFS 提速。所谓双向就是从初始状态向前扩展同时从目标状态向后扩展两边交替推进第一次相遇时两边路径拼接起来就是一条最短路径。因为搜索半径减半状态数量从 b^d 降到 2*b^(d/2)在分支因子大的问题上收益非常明显。以时钟步为例反向转移和正向转移完全对称如果正着走一步是(cur step) % M那么反着走的邻居就是(cur - step) % M或者说把每个步长取负即可。实现时只需要一个双向 BFS 模板传入正向和反向的邻居生成函数。水壶的反向动作也容易定义倒满的反面是倒空互倒的反面是以同样水量倒回去。这样无解和有解都比单向 BFS 快一个数量级。from collections import deque def bidirectional_bfs(start, is_goal, f_neighbors, b_neighbors, state_keylambda x: x): 双向 BFS返回一条最短路径无解返回 None。 if is_goal(start): return [start] f_visited {state_key(start): [start]} b_visited {} # 用一个集合保存目标的等价状态如果目标唯一则直接放一个。 # 这里简化为 start 和目标状态对称的用法具体目标由 is_goal 定义 # 反向扩展时把目标状态的每个“前驱”加入 b_visited。 f_q deque([start]) b_q deque() # 初始化反向队列需要知道目标状态不同谜题目标定义不同 # 这里用回调 batch_backward_init 简化核心策略不变。 # 实际实现中正向扩展一步反向扩展一步比较两个 visited 是否有交集。 ... return None这个骨架说明思路比完整实现更重要。我实际在时钟步上用了一个更直接的版本因为目标是一个明确状态所以反向队列初始就是目标两个 visited 字典的 key 都是当前时间点每次交替扩展一层发现某个 key 同时存在于两个 visited 时拼路径即可。对于单人象棋这种目标状态不唯一的问题双向 BFS 使用起来更麻烦所以我主要依赖对称剪枝。在 4x4 棋盘上加入对称归一化后visited 中的状态数量大约变成原来的 1/8搜索时间和内存都大幅下降。我曾经用这个技巧解开了几个 5x5 的实例这已经不是朴素 BFS 能扛住的规模了。最后说一点个人习惯写 PuzzleSolver 这类工具时我总会保留一个“暴力版”作为基准再用双向 BFS、剪枝等优化手段和它对比确认优化版本没有改变解的长度。曾经吃过一次亏加了对称剪枝后解的长度变长原因是归一化 key 时把不该合并的状态合并了。所以每做一个优化都用原始暴力版小规模验证一遍。希望帮到你。本文还有配套的精品资源点击获取
