自动解数回程序（基于Python和Ortools）

思路

第一步 定式

• 用矩阵marks表示每格在围线内（1）还是围线外（0）。首先确定哪些marks中的哪些格子必须为1，哪些格子必须为0。对于第marks[i][j]格，先用ortools建模，并给每格加上提示数约束和顶点无十字约束。最后，在假设marks[i][j]==0的情况下求marks是否有可行解，若不可解则该格必为1；反之，若假设marks[i][j]==1时marks不可解，则该格必为0。若不确定填0还是1，则保持默认值marks[i][j]=-1。
• 数回基本规则之一是要满足所有的提示数约束 。提示数约束 是指某一格四周的边数等于该提示数，若marks矩阵中相邻两格的值不相等，则它们之间会产生一条边。比如，若某格有提示数0，则代表对应格marks[i][j]的值和四周的值都相同，约束条件为组合约束AddAllowedAssignments((A[i-1][j], A[i][j-1], A[i][j], A[i][j+1], A[i+1][j]), [(0, 0, 0, 0, 0), (1, 1, 1, 1, 1)])，即这五格都是0或都是1。
• 数回基本规则之二是格子之间的顶点要么不连，要么只能连两条线（度数为0或2）。在grids里取值时还要注意满足十字约束 ，即每个顶点相邻的四条边不能同时出现（或者说顶点度数不能为4），即任意2x2区域内不能同时有一对0和一对1分别斜向相邻。相应的约束条件为组合约束AddForbiddenAssignments((A[i][j], A[i][j+1], A[i+1][j], A[i+1][j+1]), [(0, 1, 1, 0), (1, 0, 0, 1)])。
• 数回基本规则之三是连通性规则 ，即连出来的所有边都必须连通成同一回路，这个约束无法在ortools里直接表述，只能放在后面用于排除可能性。为了尽可能多地确定marks中元素的值，可以根据连通性条件先写出一些定式约束，比如禁止在marks[i][j]==0时使周围四格同时取1的包围约束，两个相邻的3的marks[i][j]的值不相等的组合提示数约束等。

第二步 突围

逐一确定grids里的哪些格必须填0、哪些格必须填1以后，盘面会变成类似这样： 回回 回 回 回回回 回 回回 回 回 回 回 ？？？回回回 回回回 ？？？？ 回 ？？？ 回 回 回 回回？回回回回回回回 回 回回 回回回 回回 回 回 回回回 为了使数回只有唯一解，此时不确定的问号格子通常已经较少。为了满足连通性规则 ，在marks里标为1的回字格也必须连通。在这一步可以把每个问号（-1）分别假设成0，然后判断剩余的1和问号是否能被连通的方式把一些问号处的突围点确定为1。确定突围点之后将返回第一步继续用ortools推，直到没有突围点可确定为止，通常这种循环只发生一次。 突围点是指，若该点为0，0会将1和问号穿插包围，导致1和问号被分割成两个及多个连通域，与基本规则矛盾。（穿插包围？西尔斯基震怒！）

第三步 枚举

循环突围之后能将问号的数量大大减少。marks中剩下的问号已经不多，直接把每种情况回代，一个个试满不满足数回三大基本规则就行了，比如上述情况只剩11个问号，它们的值只有 2 11 = 2048 2^{11}=2048 211=2048种取法。注意，marks中的1全部连通不代表围线只有一条，如果1形成“岛中湖”的形状则会产生两条围线。所以，这一步直接通过数围线条数的方式判断marks满不满足连通性规则。基本规则都满足就返回marks作为解，不满足则跳到下一种情况继续检查。 有连通性要求的谜题写起约束来真的很烦人！

代码

try: ortools except: !pip install ortools from ortools.sat.python import cp_model # 数回

puzzle为数回的谜面，每行由提示数和空格组成，不同的行之间用逗号分开

puzzle = " 02 ,230 223, 3 3 ,3 22 1, 2 2 0 2 , 2 3 3 3 ,3 10 2, 2 3 ,303 331, 02 " grid = [[char for char in row] for row in puzzle.split(’,’)] I, J = len(grid), len(grid[0]) marks = [[-1 for j in range(J)] for i in range(I)] for row in grid: for j in range(len(row)): char = row[j] row[j] = int(char) if char != ’ ’ else -1 def count_connected_ones(A): # 检查1的连通块数量 visited = [[False for _ in range(J)] for _ in range(I)] count = 0 for i in range(I): for j in range(J): if A[i][j] and not visited[i][j]: count += 1 dfs(A, visited, i, j) return count def count_loops(A): # 统计答案的环数 B = [[0 for j in range(2J+1)] for i in range(2I+1)] checked = [[0 for j in range(2J+1)] for i in range(2I+1)] def paint(i, j): if not 0<=i<2I+1 or not 0<=j<2J+1: return if not B[i][j] or checked[i][j]: return checked[i][j] = 1 if i%2==0 and j%2==1: # 横线 paint(i-1, j-1) paint(i, j-2) paint(i+1, j-1) paint(i-1, j+1) paint(i, j+2) paint(i+1, j+1) if i%2==1 and j%2==0: # 竖线 paint(i-1, j-1) paint(i-2, j) paint(i-1, j+1) paint(i+1, j-1) paint(i+2, j) paint(i+1, j+1) for i in range(I): for j in range(J): ii, jj = 2i+1, 2j+1 if i == 0 and A[i][j] == 1: B[ii-1][jj] = 1 if 0 < i < I and A[i][j] != A[i-1][j]: B[ii-1][jj] = 1 if i == I-1 and A[i][j] == 1: B[ii+1][jj] = 1 if j == 0 and A[i][j] == 1: B[ii][jj-1] = 1 if 0 < j < J and A[i][j] != A[i][j-1]: B[ii][jj-1] = 1 if j == J-1 and A[i][j] == 1: B[ii][jj+1] = 1 count = 0 for i in range(2I+1): for j in range(2J+1): if B[i][j] == 1 and not checked[i][j] and i%2 + j%2 == 1: count += 1 paint(i, j) return count def dfs(A, visited, i, j): # 深度优先搜索 stack = [(i, j)] while stack: x, y = stack.pop() if x < 0 or x >= I or y < 0 or y >= J: continue if not A[x][y] or visited[x][y]: continue visited[x][y] = True stack.append((x + 1, y)) stack.append((x - 1, y)) stack.append((x, y + 1)) stack.append((x, y - 1)) def mark_definite_ones(marks): # 标记所有突围点 for i in range(I): # 遍历所有问号 for j in range(J): if marks[i][j] == -1: marks[i][j] = 0 # 尝试将问号设置为0 count = count_connected_ones(marks) # 检查1的连通块数量 if count > 1: marks[i][j] = 1 # 如果连通块数量增加，则该问号必须是1 else: marks[i][j] = -1 return marks def render(prompt): print("\n" + prompt) for row in marks: print(’’.join([’？　回’[n+1] for n in row])) def render_line(): print("\n" + ‘-’*100 + “\n” ) def try_assume(ii=-1, jj=-1, value=-1): global marks model = cp_model.CpModel()

定义变量：(I+2)x(J+2) 网格，每个单元格的取值范围为外0内1

A = {i: {j: model.NewBoolVar(f’cell_{i}_{j}’) for j in range(-1, J+1)} for i in range(-1, I+1)} if ii != -1: model.Add(A[ii][jj] == value) # 假设某变量 for i in range(-1, I+1): for j in range(-1, J+1): if i == -1 or i == I or j == -1 or j == J: model.Add(A[i][j] == 0) # 添加约束：盘面以外的格子都在围线外 else: if marks[i][j] != -1: # 添加约束：连通区域的突破口必在围线内 model.Add(A[i][j] == marks[i][j]) model.AddForbiddenAssignments( # 添加约束：不能出现小环 (A[i-1][j], A[i][j-1], A[i][j], A[i][j+1], A[i+1][j]), [(0, 0, 1, 0, 0), (1, 1, 0, 1, 1)] ) if i < I-1 and j < J-1: # 添加约束：顶点的度数只能是0或2 model.AddForbiddenAssignments( (A[i][j], A[i][j+1], A[i+1][j], A[i+1][j+1]), [(0, 1, 1, 0), (1, 0, 0, 1)] ) if grid[i][j] == 0: # 添加约束：提示数0 model.AddAllowedAssignments( (A[i-1][j], A[i][j-1], A[i][j], A[i][j+1], A[i+1][j]), [(0, 0, 0, 0, 0), (1, 1, 1, 1, 1)] ) if grid[i][j] == 1: # 添加约束：提示数1 model.AddAllowedAssignments( (A[i-1][j], A[i][j-1], A[i][j], A[i][j+1], A[i+1][j]), [(0, 1, 1, 1, 1), (1, 0, 1, 1, 1), (1, 1, 1, 0, 1), (1, 1, 1, 1, 0), (1, 0, 0, 0, 0), (0, 1, 0, 0, 0), (0, 0, 0, 1, 0), (0, 0, 0, 0, 1) ] ) if grid[i][j] == 2: # 添加约束：提示数2 model.AddAllowedAssignments( (A[i-1][j], A[i][j-1], A[i][j], A[i][j+1], A[i+1][j]), [(1, 1, 0, 0, 0), (1, 0, 0, 1, 0), (1, 0, 0, 0, 1), (0, 1, 0, 1, 0), (0, 1, 0, 0, 1), (0, 0, 0, 1, 1), (1, 1, 1, 0, 0), (1, 0, 1, 1, 0), (1, 0, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 1, 0, 1), (0, 0, 1, 1, 1), ] ) if grid[i][j] == 3: # 添加约束：提示数3 model.AddAllowedAssignments( (A[i-1][j], A[i][j-1], A[i][j], A[i][j+1], A[i+1][j]), [(0, 1, 0, 1, 1), (1, 0, 0, 1, 1), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 0, 1, 0, 0), (0, 1, 1, 0, 0), (0, 0, 1, 1, 0), (0, 0, 1, 0, 1)] ) if i>= 1 err = False for i in range(I): for j in range(J): if i 0 and Mc[i][j] != Mc[i-1][j]: count += 1 if i < I-1 and Mc[i][j] != Mc[i+1][j]: count += 1 if i == I-1 and Mc[i][j]: count += 1 if j == 0 and Mc[i][j]: count += 1 if j > 0 and Mc[i][j] != Mc[i][j-1]: count += 1 if j < J-1 and Mc[i][j] != Mc[i][j+1]: count += 1 if j == J-1 and Mc[i][j]: count += 1 err = count != hint if err: break if err: break if err: continue if count_loops(Mc) == 1: # 最后排除回路数≠1的解 marks = Mc render(f"从2^{c}={2**c}种可能性中筛选出最终答案：") break

输出

Looking in indexes: , Requirement already satisfied: ortools in /opt/conda/envs/python35-paddle120-env/lib/python3.7/site-packages (9.5.2237) Requirement already satisfied: protobuf>=4.21.5 in /opt/conda/envs/python35-paddle120-env/lib/python3.7/site-packages (from ortools) (4.24.4) Requirement already satisfied: numpy>=1.13.3 in /opt/conda/envs/python35-paddle120-env/lib/python3.7/site-packages (from ortools) (1.19.5) Requirement already satisfied: absl-py>=0.13 in /opt/conda/envs/python35-paddle120-env/lib/python3.7/site-packages (from ortools) (2.1.0) [notice] A new release of pip available: 22.1.2 -> 24.0 [notice] To update, run: pip install –upgrade pip 题目： 02 230 223 3 3 3 22 1 2 2 0 2 2 3 3 3 3 10 2 2 3 303 331 02

已深度思考第1/10行 已深度思考第2/10行 已深度思考第3/10行 已深度思考第4/10行 已深度思考第5/10行 已深度思考第6/10行 已深度思考第7/10行 已深度思考第8/10行 已深度思考第9/10行 已深度思考第10/10行 根据提示数约束确定围内点： 回回　　　　回　　　 回　　　　回回回　回 回回　回　回　回　回 ？？？回回回　回回回 ？？？？　　　　　回 　？？？　回　回　回 回回？回回回回回回回 　回　　回回　　　　 回回回　　回回　回　 　回　　　　回回回　 确定突围点： 回回　　　　回　　　 回　　　　回回回　回 回回　回　回　回　回 ？？？回回回　回回回 ？？？？　　　　　回 　？？？　回　回　回 回回？回回回回回回回 　回　　回回　　　　 回回回　　回回　回　 　回　　　　回回回　

剩余2048种可能性 从2^11=2048种可能性中筛选出最终答案： 回回　　　　回　　　 回　　　　回回回　回 回回　回　回　回　回 　回回回回回　回回回 回回　　　　　　　回 　　　回　回　回　回 回回回回回回回回回回 　回　　回回　　　　 回回回　　回回　回　 　回　　　　回回回