スリザーリンク ― 格子点の回路として解く#
この章で学ぶこと#
スリザーリンクは、数字をヒントに1本の閉じたループを描くパズルです。ループは「格子点を結ぶ回路」なので、add_circuit() がそのまま使えます。
盤面の格子点を頂点、線を辺としてグラフにする
ループに入らない点は、自己ループ
(i, i)で表すマスの周りの線の本数を
sum(...) == 数字で縛る
ルール#
線を引く
格子点を縦横に結んで線を引きます。線は途切れたり、交差したり、枝分かれしたりしてはいけません。
数字の意味
マスの数字は、そのマスの周りの線の本数です。「0」なら線は引けません。数字のないマスは制限なし。
閉じたループを作る
すべての線がつながって、1つの閉じた輪になります。
スリザーリンクパズルのサイト
helper.puzzle.extract_slither_link() を使うと、このサイトのパズル盤面を取得できます。ブラウザの開発者ツールを開き、盤面を表す <div> タグのコードをコピーし、この関数を実行すると、盤面が配列として取得できます。
考え方#
盤面の格子点（マスの角）を頂点にする。\(h \times w\) の盤面なら、格子点は \((h+1) \times (w+1)\) 個
隣り合う格子点を結ぶ線が辺。両方向の有向辺を用意する
すべての格子点を通る必要はないので、各格子点に自己ループ
(i, i)を足すマスの周りの4本の線のうち、選ばれた本数が数字と一致するようにする
add_circuit() は「1本の回路」を作るので、ループが2つに分かれることはありません。
from ortools.sat.python import cp_model
import numpy as np
from matplotlib import pyplot as plt
from matplotlib.collections import LineCollection
from collections import defaultdict
def plot_slither_link_board(board, result=None):
"""盤面と、解いたループを描く"""
h, w = board.shape
fig, ax = plt.subplots(figsize=(w * 0.3, h * 0.3))
ax.set_ylim(-0.1, h + 0.1)
ax.set_xlim(-0.1, w + 0.1)
ax.invert_yaxis()
ax.set_aspect("equal")
all_segments = [] # 引けるすべての線（薄いグレー）
circuit_segments = [] # 選ばれた線（緑）
if result is not None:
for (n1, n2), flag in result.items():
if flag:
r1, c1 = n1 // (w + 1), n1 % (w + 1)
r2, c2 = n2 // (w + 1), n2 % (w + 1)
circuit_segments.append([(c1, r1), (c2, r2)])
for r, c in np.ndindex(h + 1, w + 1):
if r + 1 <= h:
all_segments.append([(c, r), (c, r + 1)])
if c + 1 <= w:
all_segments.append([(c, r), (c + 1, r)])
ax.add_collection(LineCollection(all_segments, color='gray', alpha=0.5))
ax.add_collection(LineCollection(circuit_segments, color='green', linewidth=2))
for (i, j), v in np.ndenumerate(board):
if v != -1:
ax.text(j + 0.5, i + 0.5, str(v), fontsize=12, va='center', ha='center')
ax.autoscale_view()
ax.axis('off')
return fig, ax
board = np.loadtxt('data/slitherlink01.txt', dtype=np.int8)
plot_slither_link_board(board);
-1 は数字のないマスです。
解く#
SlitherLinkSolver が、盤面からモデルを組み立てて解きます。
class SlitherLinkSolver:
def __init__(self, board):
self.board = board
h, w = self.board.shape
# 格子点に 0 から連番を振る
self.nodes = nodes = np.arange((h + 1) * (w + 1)).reshape(h + 1, w + 1)
# 隣り合う格子点を結ぶ有向辺（両方向）
self.edges = edges = []
for (r, c), s in np.ndenumerate(nodes):
if c + 1 <= w:
e = nodes[r, c + 1]
edges.extend([(s, e), (e, s)])
if r + 1 <= h:
e = nodes[r + 1, c]
edges.extend([(s, e), (e, s)])
# 各マスの周りの4本の線（両方向で8個）を集める
self.cell_edges = cell_edges = defaultdict(set)
for (r, c), _ in np.ndenumerate(board):
n1 = nodes[r, c]
n2 = nodes[r, c + 1]
n3 = nodes[r + 1, c]
n4 = nodes[r + 1, c + 1]
for edge in [(n1, n2), (n1, n3), (n2, n4), (n3, n4)]:
cell_edges[r, c].add(edge)
cell_edges[r, c].add(edge[::-1])
model = cp_model.CpModel()
variables = {e: model.new_bool_var(f'edge{e}') for e in edges}
# 通らない格子点を表す自己ループ
dummies = [(i, i, model.new_bool_var(f'dummy_{i}'))
for i in range((h + 1) * (w + 1))]
model.add_circuit([(s, e, v) for (s, e), v in variables.items()] + dummies)
# マスの周りの線の本数
for (r, c), count in np.ndenumerate(board):
if count != -1:
box_edges = [variables[edge] for edge in cell_edges[r, c]]
model.add(sum(box_edges) == int(count))
solver = cp_model.CpSolver()
if solver.solve(model) not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
raise ValueError("解が見つかりませんでした")
self.result = {key: solver.value(val) for key, val in variables.items()}
solver = SlitherLinkSolver(board)
plot_slither_link_board(board, solver.result);
コードの説明#
1. 格子点に番号を振る
\(h \times w\) の盤面には \((h+1) \times (w+1)\) 個の格子点があります。2次元のまま扱うと面倒なので、np.arange() で 0 から連番を振って1次元の ID にします。
2. 辺を作る
各格子点から「右」と「下」に辺を張り、両方向を追加します。add_circuit() は有向辺を扱うので、行きと帰りの両方が必要です。
3. マスの周りの線を集める
マス (r, c) の四隅の格子点から、(上・左・右・下) の4本の線を取り出します。両方向を入れて8個になりますが、これは後で「何本選ばれたか」を数えるときに、向きに関係なく数えられるようにするためです（1本の線は片方向しか選ばれないので、和は本数になります）。
4. 自己ループで「通らない点」を表す
すべての格子点がループに使われるわけではありません。(i, i, var) を足すと、その点を使わない（自己ループで済ませる）選択ができます。
5. 数字の制約
model.add(sum(box_edges) == int(count))
マスの周りの線の本数が、数字と一致するようにします。
もっと難しいパズル#
パズルサイトの最難関クラスを解いてみます。
board = np.loadtxt('data/slitherlink02.txt', dtype=np.int8)
solver = SlitherLinkSolver(board)
plot_slither_link_board(board, solver.result);
検算#
解いたループが条件を満たしているか、確かめます。
def check_slither(board, result):
"""各マスの線の本数と、ループが1本かどうかを確認する"""
h, w = board.shape
lines = set()
for (n1, n2), flag in result.items():
if flag:
lines.add(tuple(sorted((n1, n2))))
# 1. 各マスの周りの線の本数
for (r, c), count in np.ndenumerate(board):
if count == -1:
continue
n1 = r * (w + 1) + c
n2, n3, n4 = n1 + 1, n1 + w + 1, n1 + w + 2
box = [tuple(sorted(e)) for e in [(n1, n2), (n1, n3), (n2, n4), (n3, n4)]]
if sum(1 for e in box if e in lines) != count:
return False, f"マス {(r, c)} の本数が違います"
# 2. ループが1本か（次数2の点をたどって一周できるか）
adj = defaultdict(list)
for a, b in lines:
adj[a].append(b)
adj[b].append(a)
for node, nb in adj.items():
if len(nb) != 2:
return False, f"格子点 {node} の次数が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, "ループが1本ではありません"
return True, f"{count} 個の点を通る1本のループです"
print(check_slither(solver.board, solver.result))
(True, '782 個の点を通る1本のループです')
まとめ#
格子点を頂点、線を辺にすると、スリザーリンクは「1本の回路を探す問題」になる
通らない点は自己ループ
(i, i)で表すマスの周りの線は、8本（両方向）の和で数えられる
add_circuit()が「1本のループ」を保証してくれるので、ループが分裂しない出てきた解は、検算のコードで確かめる