ましゅ（Masyu）― 丸の制約を辺で書く#
この章で学ぶこと#
ましゅは、白丸と黒丸を1本のループが通るパズルです。ループの形は add_circuit() で作れますが、丸の前後で曲がる／直進するという条件は自分で書く必要があります。
有向辺（回路用）と無向辺（制約用）を対応させる
「横の線の本数 − 縦の線の本数」で曲がりを判定する
白丸＝直進、黒丸＝直角、その前後は黒丸の隣で曲がらない
ルール#
盤面に線を引いて、全体で1つの輪を作る。
線はマスの中央を通り、交差・枝分かれはしない。
線はすべての白丸と黒丸を通る。
白丸を通る線は、白丸のマスで必ず直進し、隣のマスで直角に曲がる（片側だけでもよい）。
黒丸を通る線は、黒丸のマスで必ず直角に曲がり、隣のマスでは曲がらない。
ましゅパズルのサイト
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]]
考え方#
すべての丸を通る1本のループなので、add_circuit() が使えます。ただし、通らないマスがあるので、丸のないマスには自己ループ (i, i) を足します。
add_circuit() の辺は有向です。隣り合うマス a, b は a → b と b → a の2本で結び、回路はどちらか一方だけを選びます。
一方、丸の条件（曲がる・直進する）は向きを考えずに書きたいので、有向辺 e1, e2 から無向辺 e を作ります。
model.add(e == e1 + e2) # どちらか一方が真なら、無向辺は「線がある」
これで、丸のマスの周りの線を、上下左右の4本（無向）として扱えます。
丸のマスについて、1マス先の線を \(U_1, D_1, L_1, R_1\)、2マス先の線を \(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()])
# 無向辺 = 2本の有向辺のどちらか
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:
# 2マス先が盤の外なら、その方向には進めない
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):
"""丸のマスで直進・直角になっているか、1本のループかを確認する"""
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. ループが1本か
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, "ループが1本ではありません"
return True, f"{count} マスを通る1本のループです"
print(check_masyu(puzzle, route))
(True, '536 マスを通る1本のループです')
まとめ#
ループは
add_circuit()。通らないマスは自己ループ(i, i)で表す有向辺 2 本を
e == e1 + e2で無向辺にまとめると、丸の条件が書きやすい「曲がったか」は
L + R - U - Dが 0 かどうかで判定できる黒丸では、隣のマスで曲がらないことも
add_implication()で明示する盤の外に出る方向は
0（線なし）として式に混ぜる