Yin-Yangパズル ― 色の連結を整数の番号で表す

Yin-Yangパズル ― 色の連結を整数の番号で表す#

この章で学ぶこと#

Yin-Yang は、盤面を白と黒で塗り分けるパズルです。add_circuit() のような既成の制約がないので、自分でモデルを組み立てます。

  • 各マスに「色」と「辿った順番」の2つの変数を持たせる

  • 隣り合う同じ色のマスは、必ずどちらかの向きの辺でつなぐ

  • 番号が増える向きに辺を張ることで、同じ色がすべてつながる

  • 同じ色の2×2を作らない

ルール#

長方形のグリッドで、一部のマスには最初から黒か白の碁石が置かれています。残りのマスを塗って、次の条件を満たします。

  1. すべての黒マスが、上下左右のつながりで1つのグループになる

  2. すべての白マスが、上下左右のつながりで1つのグループになる

  3. 同じ色の2×2の塊を作ってはいけない

中心に点があるマスが、最初からある碁石です。

Yin-Yangパズルのサイト

https://www.puzzle-yin-yang.com/

helper.puzzle.extract_yinyan() を使うと、このサイトのパズル盤面を取得できます。ブラウザの開発者ツールを開き、盤面を表す <div> タグのコードをコピーし、この関数を実行すると、盤面が配列として取得できます。

盤面#

1 が白の碁石、2 が黒の碁石、0 が空きマスです。

import numpy as np

puzzle = np.loadtxt('data/yinyang01.txt', dtype=np.uint8)
print(puzzle)

[[0 0 0 0 0 0]
 [0 0 1 0 0 0]
 [0 0 0 1 0 0]
 [0 0 0 0 0 0]
 [0 2 0 0 0 0]
 [1 0 2 1 0 0]]

from ortools.sat.python import cp_model
import numpy as np
from collections import defaultdict

考え方#

各マスに、次の2つの変数を持たせます。

変数

意味

colors[r, c]（ブール）

偽なら白、真なら黒

steps[r, c]（整数）

同じ色の中で「何番目に辿ったか」

さらに、隣り合うマスの間に有向辺を用意します。edge12 は「マス1 → マス2」、edge21 はその逆です。制約は次の7つです。

  1. 両方向は選ばない … edge12 と edge21 が同時に真にならない

  2. 辺があるなら同じ色 … edge12 なら color1 == color2

  3. 同じ色なら必ず辺がある … color1 == color2 なら edge12 か edge21 のどちらか

  4. 向きと番号 … edge12 なら step1 < step2

  5. 各マスの入り口は1つ … スタート以外は、入ってくる辺がちょうど1本

  6. スタートは入り口なし … 白と黒のスタート地点は、入ってくる辺が0本

  7. 2×2を禁止 … 4マスが同じ色にならない

2と3を合わせると「同じ色のマス同士は必ずつながっている」になります。4と5で、スタートから番号が増える向きに辺をたどると、すべてのマスにたどり着けます。つまり同じ色が1つのグループになるわけです。

スタート地点は、白・黒それぞれ1つ適当に選びます（色ごとに1本の木を作るイメージです）。

def solve_yinyang(puzzle):
    """Yin-Yang を解いて (色, 番号, 選ばれた辺) を返す"""
    model = cp_model.CpModel()
    h, w = puzzle.shape
    edges = []

    colors = {}
    steps = {}

    for (r, c), v in np.ndenumerate(puzzle):
        colors[r, c] = model.new_bool_var(f'color_{r}_{c}')
        steps[r, c] = model.new_int_var(0, h * w, f'step_{r}_{c}')
        if c + 1 < w:
            edges.extend([(r, c, r, c + 1), (r, c + 1, r, c)])
        if r + 1 < h:
            edges.extend([(r, c, r + 1, c), (r + 1, c, r, c)])

    edge_variables = {e: model.new_bool_var(f'edge_{e}') for e in edges}

    out_edges = defaultdict(list)
    in_edges = defaultdict(list)
    for e in edges:
        out_edges[e[:2]].append(e)
        in_edges[e[2:]].append(e)

    # スタート地点（白・黒それぞれ最初の碁石）
    whites = np.where(puzzle == 1)
    blacks = np.where(puzzle == 2)
    start_locs = [(whites[0][0], whites[1][0]), (blacks[0][0], blacks[1][0])]

    for (r1, c1, r2, c2) in edges:
        n1, n2 = (r1, c1), (r2, c2)
        if n1 > n2:
            continue        # 各ペアを1回だけ扱う

        cell1, cell2 = colors[n1], colors[n2]
        step1, step2 = steps[n1], steps[n2]
        edge12, edge21 = edge_variables[r1, c1, r2, c2], edge_variables[r2, c2, r1, c1]

        # 1. 両方向は選ばない
        model.add_bool_or(~edge12, ~edge21)
        # 2. 辺があるなら同じ色（4通りの組み合わせを CNF で書く）
        model.add_bool_or(~cell1, cell2, ~edge12)
        model.add_bool_or(cell1, ~cell2, ~edge12)
        model.add_bool_or(~cell1, cell2, ~edge21)
        model.add_bool_or(cell1, ~cell2, ~edge21)
        # 3. 同じ色なら、どちらかの向きの辺がある
        model.add_bool_or(cell1, cell2, edge12, edge21)
        model.add_bool_or(~cell1, ~cell2, edge12, edge21)
        # 4. 辺の向きに沿って番号が増える
        model.add(step1 < step2).only_enforce_if(edge12)
        model.add(step1 > step2).only_enforce_if(edge21)

    for (r, c), v in np.ndenumerate(puzzle):
        in_vars = [edge_variables[e] for e in in_edges[r, c]]
        out_vars = [edge_variables[e] for e in out_edges[r, c]]

        if (r, c) not in start_locs:
            # 5. スタート以外は、入ってくる辺がちょうど1本
            model.add(sum(in_vars) == 1)
            model.add(steps[r, c] > 0)
        else:
            # 6. スタートは入り口なし、出口は1本以上
            model.add(sum(in_vars) == 0)
            model.add(sum(out_vars) > 0)
            model.add(steps[r, c] == 0)

        # 碁石の色を固定する
        if v == 1:
            model.add_bool_and(~colors[r, c])
        elif v == 2:
            model.add_bool_and(colors[r, c])

    # 7. 同じ色の2×2を作らない
    for r in range(h - 1):
        for c in range(w - 1):
            quad = [colors[r, c], colors[r + 1, c], colors[r, c + 1], colors[r + 1, c + 1]]
            model.add_bool_or(quad)                        # 全部白はダメ
            model.add_bool_or([~v for v in quad])          # 全部黒もダメ

    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 120
    status = solver.solve(model)
    print("status:", solver.status_name(status))

    cells = {key: solver.value(val) for key, val in colors.items()}
    numbers = {key: solver.value(val) for key, val in steps.items()}
    chosen = [key for key, val in edge_variables.items() if solver.value(val)]
    return cells, numbers, chosen

補足：CNF で書いている理由#

model.add(cell1 == cell2).only_enforce_if(edge12) のようにも書けますが、比較式を条件付きにする形は CP-SAT が解きにくいことがあります。そこで「〜または〜」の形（CNF）に展開して与えています。

  • ~edge12 | ~edge21 … 2つ同時に成り立たない

  • ~cell1 | cell2 | ~edge12 … edge12 なら cell1 → cell2

  • cell1 | ~cell2 | ~edge12 … edge12 なら cell2 → cell1

この2つで「edge12 なら cell1 == cell2」になります。

描画#

色を塗り、番号と辺を重ねて表示します。

from matplotlib import pyplot as plt
from matplotlib.collections import LineCollection


def plot_yinyang(puzzle, cells=None, numbers=None, edges=None, scale=0.3):
    h, w = puzzle.shape
    fig, ax = plt.subplots(figsize=(w * scale, h * scale))

    if cells is not None:
        xs, ys, colors = [], [], []
        for (y, x), v in cells.items():
            xs.append(x)
            ys.append(y)
            colors.append('white' if v == 0 else 'black')
        ax.scatter(xs, ys, s=80 * scale / 0.1, c=colors)

    if numbers:
        for (r, c), num in numbers.items():
            color = 'black' if cells[r, c] == 0 else 'white'
            ax.text(c, r, str(num), color=color, size=9)

    if edges:
        segments = []
        for r1, c1, r2, c2 in edges:
            segments.append([(c1, r1), (c2, r2)])
        ax.add_collection(LineCollection(segments, alpha=0.7))

    y, x = np.where(puzzle == 1)
    ax.scatter(x, y, s=8, edgecolor="#000000", facecolor="none")

    y, x = np.where(puzzle == 2)
    ax.scatter(x, y, s=8, edgecolor="#ffffff", facecolor="none")

    ax.set_aspect('equal')
    fig.patch.set_facecolor('#777777')
    ax.set_xlim(-0.5, w - 0.5)
    ax.set_ylim(-0.5, h - 0.5)
    ax.invert_yaxis()
    ax.axis('off')
    return fig, ax

問題を解く#

パズルサイトの実際の問題を解いてみます。

%%time
puzzle = np.loadtxt('data/yinyang02.txt', dtype=np.uint8)
cells, numbers, edges = solve_yinyang(puzzle)
plot_yinyang(puzzle, cells=cells);

status: OPTIMAL
CPU times: total: 1.44 s
Wall time: 253 ms
_images/1b5a00ff84eb03a219ee28a70eaddb9d7beb814ecfd555a054fc0d6e530fa873.png

もっと大きな問題（25×25）は、かなり時間がかかります。

%%time
puzzle = np.loadtxt('data/yinyang03.txt', dtype=np.uint8)
cells, numbers, edges = solve_yinyang(puzzle)
plot_yinyang(puzzle, cells=cells);

status: OPTIMAL
CPU times: total: 4min 49s
Wall time: 26.9 s
_images/11c8fec672e6424261626e772caa447bf7dd5cd0a97519aa86dda2f419a331a5.png

検算#

2色がそれぞれ連結しているか、2×2ができていないかを確かめます。

def check_yinyang(puzzle, cells):
    h, w = puzzle.shape
    grid = np.array([[cells[r, c] for c in range(w)] for r in range(h)])

    # 3. 同じ色の2×2がない
    for r in range(h - 1):
        for c in range(w - 1):
            quad = grid[r:r+2, c:c+2]
            if quad.min() == quad.max():
                return False, f"同じ色の2×2があります {(r, c)}"

    # 1, 2. 各色が連結
    for color, name in ((0, "白"), (1, "黒")):
        points = {(r, c) for r in range(h) for c in range(w) if grid[r, c] == color}
        if not points:
            continue
        start = next(iter(points))
        seen = {start}
        stack = [start]
        while stack:
            r, c = stack.pop()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nb = (r + dr, c + dc)
                if nb in points and nb not in seen:
                    seen.add(nb)
                    stack.append(nb)
        if seen != points:
            return False, f"{name}が2つ以上に分かれています"

    return True, "2色とも連結していて、2×2もありません"


print(check_yinyang(puzzle, cells))

(True, '2色とも連結していて、2×2もありません')

まとめ#

  • 色と「辿った順番」の2つの変数で、色の連結を表現できる

  • 同じ色のマス同士は必ずどちらかの向きの辺でつなぐ。番号は辺の向きに増える

  • 各マスの入り口を1本にすると、スタートからたどって全マスに届く（＝連結）

  • 2×2の禁止は、4マスの OR と、その否定の OR で書ける

  • 比較式を条件付きにするのは苦手なので、CNF に展開して add_bool_or で与える

  • 25×25 のような大きな盤面は、それなりの時間がかかる（時間制限も指定できる）

パズルサイトには片方の色の碁石しかない盤面もあります。スタート地点を色ごとに選んでいるので、その場合は「もう片方の色のスタートをどう決めるか」を工夫する必要があります。