珍珠 Masyu：用边写出圆圈的约束#
本章的内容#
珍珠是让一条回路穿过白圆与黑圆的谜题，回路的形状可以用 add_circuit() 造出，而圆的前后要转弯还是直行，这一条件需要自己写。
把有向边，即回路用的边，与无向边，即约束用的边对应起来
用横线条数减竖线条数判断是否转弯
白圆直行、黑圆转弯，黑圆前后相邻的格又不转弯
圆的条件写成约束之后，判断与画线都交给求解器。
规则#
在盘面上画线，整体构成一个环。
线经过格的中央，不交叉也不分叉。
线要穿过所有白圆与黑圆。
穿过白圆的线，在白圆所在的格必定直行，并在相邻的格直角转弯，任一侧转弯即可。
穿过黑圆的线，在黑圆所在的格必定直角转弯，而在相邻的格不转弯。
规则里的“白圆直行、黑圆转弯”是唯一需要自己翻译的部分，其余都由 add_circuit() 负责。
珍珠谜题的网站
用 helper.puzzle.extract_masyu() 可以取得这个网站上的谜题盘面。打开浏览器的开发者工具，把表示盘面的 <div> 标签的代码复制下来，交给这个函数执行，盘面就会以数组的形式取得。
盘面#
1 是白圆，2 是黑圆，0 是什么都没有的格。盘面以二维数组给出，数字与圆的对应只由这三个取值定义。
from ortools.sat.python import cp_model
import numpy as np
puzzle = np.loadtxt('data/masyu01.txt', dtype=np.uint8)
print(puzzle)
[[0 1 0 0 1 0 0 2]
[0 0 0 0 0 1 0 0]
[0 0 2 0 0 1 0 0]
[0 0 1 0 1 1 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0]
[0 2 0 0 1 0 0 0]
[0 0 0 1 0 0 0 2]]
思路#
回路要穿过所有圆，因此可以用 add_circuit()；对于回路不经过的格，则加上自环 (i, i)。
add_circuit() 的边是有向的。相邻的格 a 与 b 用 a → b 与 b → a 两条边连接，回路只选其中一条。
另一方面，圆的条件，即转弯与直行，希望不区分方向来写，因此由有向边 e1、e2 造出无向边 e。
model.add(e == e1 + e2) # 只要其中一条为真，无向边就“有线段”
这样，圆所在格周围的线就可以按上下左右四条无向线处理。无向边的真假由两条有向边决定，转换只在一处发生。
对圆所在的格，把一格之外的线记为 \(U_1, D_1, L_1, R_1\)，两格之外的线记为 \(U_2, D_2, L_2, R_2\)。
是否转弯可以用下面的式子判断。
直行，左右：\(1+1-0-0 = 2\)
直行，上下：\(0+0-1-1 = -2\)
直角，例如左加上：\(1+0-1-0 = 0\)
也就是等于 0 表示转弯，不等于 0 表示直行，这个式子只看四条边的真假，不必分方向讨论。
圆 |
条件 |
|---|---|
白圆 |
\(L_1 + R_1 - U_1 - D_1 \neq 0\)，即直行 |
黑圆 |
\(L_1 + R_1 - U_1 - D_1 = 0\)，即直角 |
黑圆还要求相邻的格不转弯，因此要加上 \(L_1 \rightarrow L_2\) 这样的蕴含，即从黑圆引出的线在下一格直行。四个方向各要一条这样的蕴含，黑圆前后的格才都保持直行。
def solve_masyu(puzzle):
"""求解珍珠谜题，返回用到的有向边列表"""
h, w = puzzle.shape
nodes = np.arange(h * w).reshape(h, w)
# 有向边（用于回路）和无向边（用于圆的条件）
directed_edges = []
edges = []
for (r, c), n1 in np.ndenumerate(nodes):
if c + 1 < w:
n2 = nodes[r, c + 1]
directed_edges.extend([(n1, n2), (n2, n1)])
edges.append((n1, n2))
if r + 1 < h:
n2 = nodes[r + 1, c]
directed_edges.extend([(n1, n2), (n2, n1)])
edges.append((n1, n2))
model = cp_model.CpModel()
directed_edge_variables = {e: model.new_bool_var(f'dedge_{e}') for e in directed_edges}
edge_variables = {e: model.new_bool_var(f'edge_{e}') for e in edges}
# 没有圆的方格可以脱离回路（自环）
dummy_variables = {(i, i): model.new_bool_var(f'dummy_{i}')
for (r, c), i in np.ndenumerate(nodes) if puzzle[r, c] == 0}
model.add_circuit(
[(n1, n2, v) for (n1, n2), v in directed_edge_variables.items()] +
[(n1, n2, v) for (n1, n2), v in dummy_variables.items()])
# 无向边 = 两条有向边中的一条
for (n1, n2), b in edge_variables.items():
model.add(b == directed_edge_variables[n1, n2] + directed_edge_variables[n2, n1])
directs = dict(u=(-1, 0), d=(1, 0), l=(0, -1), r=(0, 1))
for (r, c), num in np.ndenumerate(puzzle):
node = nodes[r, c]
step1 = {}
step2 = {}
for name, (dr, dc) in directs.items():
r1, c1 = r + dr, c + dc
r2, c2 = r + dr * 2, c + dc * 2
if 0 <= r1 < h and 0 <= c1 < w:
n1, n2 = sorted([node, nodes[r1, c1]])
step1[name] = edge_variables[n1, n2]
if 0 <= r2 < h and 0 <= c2 < w:
n1, n2 = sorted([nodes[r1, c1], nodes[r2, c2]])
step2[name] = edge_variables[n1, n2]
# 通向盘外的方向当作 0（没有线）
l, r_, u, d = [step1.get(direction, 0) for direction in 'lrud']
expr = l + r_ - u - d
if num == 1: # 白圆：直行
model.add(expr != 0)
elif num == 2: # 黑圆：直角
model.add(expr == 0)
for direction in "lrud":
if direction in step2:
# 从黑圆出来的线，在下一格不转弯
model.add_implication(step1[direction], step2[direction])
elif direction in step1:
# 两格之外在盘外，就不能往这个方向走
model.add_bool_and(~step1[direction])
solver = cp_model.CpSolver()
if solver.solve(model) not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
raise ValueError("没有找到解")
return [key for key, v in directed_edge_variables.items() if solver.value(v)]
绘制#
画出盘面与回路，圆与线的位置要与盘面对齐。
from matplotlib import pyplot as plt
from matplotlib.collections import LineCollection
def plot_masyu_board(puzzle, route):
"""画出盘面和回路"""
h, w = puzzle.shape
fig, ax = plt.subplots(figsize=(w * 0.3, h * 0.3))
segments = []
for n1, n2 in route:
r1, c1 = n1 // w, n1 % w
r2, c2 = n2 // w, n2 % w
segments.append([(c1, r1), (c2, r2)])
ax.add_collection(LineCollection(segments, color='black'))
r, c = np.where(puzzle == 1)
ax.scatter(c, r, s=100, marker='o', facecolor="none", edgecolor="black")
r, c = np.where(puzzle == 2)
ax.scatter(c, r, s=100, marker='o', facecolor="black", edgecolor="black")
ax.set_aspect('equal')
ax.invert_yaxis()
ax.axis('off')
return fig, ax
简单的盘面#
puzzle = np.loadtxt('data/masyu01.txt', dtype=np.uint8)
route = solve_masyu(puzzle)
plot_masyu_board(puzzle, route);
最难的盘面#
puzzle = np.loadtxt('data/masyu02.txt', dtype=np.uint8)
route = solve_masyu(puzzle)
plot_masyu_board(puzzle, route);
验算#
确认解出的回路是否满足各个圆的条件，验算时把每个圆的类型与通过方向逐一对照。
def check_masyu(puzzle, route):
"""确认圆所在的格是否直行或直角，以及回路是否只有一条"""
h, w = puzzle.shape
adj = {}
for n1, n2 in route:
adj.setdefault(n1, []).append(n2)
adj.setdefault(n2, []).append(n1)
def step(n1, n2):
r1, c1 = divmod(n1, w)
r2, c2 = divmod(n2, w)
return r2 - r1, c2 - c1
# 1. 是否经过圆所在的格，并满足条件
for (r, c), v in np.ndenumerate(puzzle):
if v == 0:
continue
node = r * w + c
if node not in adj or len(adj[node]) != 2:
return False, f"圆 {(r, c)} 没有被经过"
d1, d2 = (step(node, adj[node][0]), step(node, adj[node][1]))
horizontal = d1[0] == 0 and d2[0] == 0
vertical = d1[1] == 0 and d2[1] == 0
if v == 1 and not (horizontal or vertical):
return False, f"白圆 {(r, c)} 处不是直行"
if v == 2 and (horizontal or vertical):
return False, f"黑圆 {(r, c)} 处不是直角"
# 2. 回路是否只有一条
start = next(iter(adj))
prev, cur, count = None, start, 0
while True:
count += 1
nxt = adj[cur][0] if adj[cur][0] != prev else adj[cur][1]
prev, cur = cur, nxt
if cur == start:
break
if count != len(adj):
return False, "回路不是一条"
return True, f"{count} 个方格组成的一条回路"
print(check_masyu(puzzle, route))
(True, '544 个方格组成的一条回路')
小结#
回路用
add_circuit()，不经过的格用自环(i, i)表示把两条有向边用
e == e1 + e2合成无向边之后，圆的条件就容易写了是否转弯可以用
L + R - U - D是否等于 0 判断黑圆还要求相邻的格不转弯，这条约束要用
add_implication()明确写出通向盘外的方向按
0处理，即视为没有线，代入式子即可