ノノグラム

ノノグラムは、マス目のいくつかを黒く塗って絵を完成させるパズルで、お絵かきロジックとも呼ばれます。 各行の左と各列の上には、その行（列）にある黒マスの塊の長さが、左から（上から）順に書かれています。 例えば「2 5 2」は、長さ 2、5、2 の黒マスの塊がこの順に並び、塊と塊の間には白マスが 1 個以上あることを表します。 「0」は、その行（列）に黒マスがないことを表します。 すべての手がかりを満たすように、塗るマスを決めます。

ここでは次の $15\times 15$ の問題を解きます（行数 $H=15$、列数 $W=15$）:

塊の開始位置

長さ $n$ の 1 本の行（または列）を考え、手がかりを $(L_0, L_1, \ldots, L_{m-1})$ とします。 位置は左端（上端）を $0$ として数えます。 塊 $k$ が位置 $s_k$ から始まるとすると、塊の並びが手がかりに合う条件は

\[\begin{aligned} s_0\geq 0,\qquad s_{k+1}\geq s_k+L_k+1\ \ (0\leq k\leq m-2),\qquad s_{m-1}+L_{m-1}\leq n \end{aligned}\]

です。真ん中の不等式は、塊 $k$ の後に白マスが 1 個以上あってから塊 $k+1$ が始まることを表します。

すべての塊を左に詰めると、塊 $k$ は位置

\[e_k=\sum_{l=0}^{k-1}(L_l+1)\]

から始まり、右には

\[d=n-\sum_{l=0}^{m-1}L_l-(m-1)\]

個のマスが余ります。これを余白と呼びます。 各塊は位置 $e_k$ から $e_k+d$ までのどこかで始まります。

変数: 塊が位置 $j$ までに始まっているか

開始位置 $s_k$ を直接表す代わりに、各塊 $k$ と $0\leq p\leq d-1$ について、次のバイナリ変数を使います:

\[a_{k,p}=1 \iff s_k\leq e_k+p\]

つまり $a_{k,p}=1$ は「塊 $k$ は位置 $e_k+p$ までに始まっている」ことを表します。 $p$ を増やしていくと、$a_{k,p}$ は $0,\ldots,0,1,\ldots,1$ の形になり、$0$ の個数 $s_k-e_k$ が、左に詰めた位置からのずれになります。 $0$ と $1$ の境目を 1 つずらす（変数を 1 個反転する）と、塊が 1 マス動きます。 このように、整数（ここでは開始位置）を「ある値以下か」を表すバイナリ変数の列で表す方法は、順序符号化と呼ばれます。

例えば $n=10$、手がかり $(3, 1)$ の行では、$e_0=0$、$e_1=4$、$d=10-4-1=5$ です。 次の塗り方では $s_0=2$、$s_1=8$ です:

j   0 1 2 3 4 5 6 7 8 9
    . . # # # . . . # .

このとき変数の値は次のようになります:

$p$	0	1	2	3	4
$a_{0,p}$（位置 $0+p$ までに始まっている）	0	0	1	1	1
$a_{1,p}$（位置 $4+p$ までに始まっている）	0	0	0	0	1

$a$ で表せる開始位置は $e_k$ から $e_k+d$ までなので、塊が行の端からはみ出すことはありません。

制約

1 本の行（列）について、次の 2 種類の制約を課します。

• 一度始まった塊は、その先の位置でも「始まっている」:

\[\begin{aligned} a_{k,p}\leq a_{k,p+1} && (0\leq k\leq m-1,\ 0\leq p\leq d-2) \end{aligned}\]

• 塊 $k+1$ は塊 $k$ より後に始まる:

\[\begin{aligned} a_{k+1,p}\leq a_{k,p} && (0\leq k\leq m-2,\ 0\leq p\leq d-1) \end{aligned}\]

2 つ目は条件 $s_{k+1}\geq s_k+L_k+1$ を書き直したものです。 $e_{k+1}=e_k+L_k+1$ なので、この条件は $s_{k+1}-e_{k+1}\geq s_k-e_k$、 つまり「塊 $k+1$ のずれは塊 $k$ のずれ以上」と同じです。 ずれは $0$ の個数なので、これは各 $p$ で $a_{k+1,p}\leq a_{k,p}$ が成り立つことと同値です。 上の例でも $a_{1,p}\leq a_{0,p}$ がすべての $p$ で成り立っています。

次に、各位置の色を変数で表します。 「塊 $k$ が位置 $j$ までに始まっている」を、すべての位置 $j$ に広げて

\[A_k(j)=\begin{cases} 0 & (j<e_k)\\ a_{k,\,j-e_k} & (e_k\leq j<e_k+d)\\ 1 & (j\geq e_k+d) \end{cases}\]

とします。塊 $k$ が位置 $j$ を覆うのは、塊 $k$ が位置 $j$ までに始まっていて、位置 $j-L_k$ までには始まっていないときなので、 位置 $j$ の色（黒なら $1$、白なら $0$）は

\[B(j)=\sum_{k=0}^{m-1}\bigl(A_k(j)-A_k(j-L_k)\bigr)\]

と書けます。上の 2 種類の制約を満たせば塊は重ならないので、$B(j)$ は $0$ か $1$ です。 上の例の位置 $8$ では、$A_1(8)-A_1(7)=a_{1,4}-a_{1,3}=1-0=1$ で黒になります。

最後に、マス $(i,j)$ の色を表すバイナリ変数 $x_{i,j}$ を用意します。 行 $i$ について求めた $B(j)$ を $R_{i,j}$、列 $j$ について求めた $B(i)$ を $C_{i,j}$ と書き、 行から見た色と列から見た色がどちらも $x_{i,j}$ に等しいという制約を課します:

\[\begin{aligned} R_{i,j}=x_{i,j},\qquad C_{i,j}=x_{i,j} && (0\leq i\leq H-1,\ 0\leq j\leq W-1) \end{aligned}\]

制約はすべて線形の等式・不等式で、補助変数は必要ありません。

PyQBPP プログラム

以下のプログラムは、上記の制約を ネイティブ制約 qbpp.cons() で宣言し、 Easy Solver でパズルを解きます:

import pyqbpp as qbpp

# 手がかり: 各行 (上から) と各列 (左から) の黒マスの塊の長さ。
ROWS = [[], [1, 1], [2, 2], [3, 3], [13], [13], [2, 5, 2], [2, 5, 2],
        [13], [6, 6], [5, 5], [11], [9], [5], []]
COLS = [[], [10], [10], [3, 5], [2, 5], [10], [6, 3], [5, 3],
        [6, 3], [10], [2, 5], [3, 5], [10], [10], []]
H, W = len(ROWS), len(COLS)


# 長さ n の行 (列) の変数 a[k, p]。
def line_var(name, clue, n):
    d = n - sum(clue) - len(clue) + 1  # 余白: 塊を左に詰めたときに右に余るマスの数
    return qbpp.var(name, shape=(len(clue), d))


# 塊 k が位置 j までに始まっていれば 1 になる式。
def started(a, clue, k, j):
    p = j - (sum(clue[:k]) + k)  # 位置 j と、塊 k が始まれる最も左の位置との差
    if p < 0:
        return 0
    if p >= a.shape[1]:
        return 1
    return a[k, p]


# 位置 j が黒なら 1 になる式。
def black(a, clue, j):
    e = 0
    for k in range(len(clue)):
        e += started(a, clue, k, j) - started(a, clue, k, j - clue[k])
    return e


# 1 本の行 (列) の塊の並びの制約。
def line_cons(a):
    m, d = a.shape
    g = 0
    for k in range(m):
        for p in range(d - 1):
            g += qbpp.cons(a[k, p + 1] - a[k, p] >= 0)  # 始まった塊は、その先でも始まっている
    for k in range(m - 1):
        for p in range(d):
            g += qbpp.cons(a[k, p] - a[k + 1, p] >= 0)  # 塊 k+1 は塊 k より後に始まる
    return g


x = qbpp.var("x", shape=(H, W))
row = [line_var(f"r{i}", ROWS[i], W) for i in range(H)]
col = [line_var(f"c{j}", COLS[j], H) for j in range(W)]

f = 0
for a in row + col:
    f += line_cons(a)
for i in range(H):
    for j in range(W):
        f += qbpp.cons(black(row[i], ROWS[i], j) - x[i, j] == 0)  # 行から見た色
        f += qbpp.cons(black(col[j], COLS[j], i) - x[i, j] == 0)  # 列から見た色

sol = qbpp.EasySolver(f).search(target_energy=0)
for i in range(H):
    print("".join("#" if sol(x[i, j]) else "." for j in range(W)))

手がかりはリストのリストで与えます。「0」の行（列）は空のリスト [] です。

• line_var(name, clue, n) は、長さ n の行（列）の変数 $a_{k,p}$ を、形 $(m, d)$ の 2 次元配列として作ります。 手がかりが空のリストの行（列）では $m=0$ なので、要素のない配列になります。
• started(a, clue, k, j) は $A_k(j)$ を返します。位置によって 0、1、変数 a[k, p] のいずれかになります。
• black(a, clue, j) は位置 j の色 $B(j)$ を表す式を返します。
• line_cons(a) は、1 本の行（列）について 2 種類の不等式制約を qbpp.cons() で宣言した式を返します。 変数どうしの大小は、差を取って a[k, p + 1] - a[k, p] >= 0 の形で書きます。

qbpp.var("x", shape=(H, W)) はマスの色を表す変数 $x_{i,j}$ の配列です。 row[i] は行 $i$ の変数 $a$、col[j] は列 $j$ の変数 $a$ です。 最後の二重ループで、各マスについて行から見た色と列から見た色がどちらも x[i, j] に等しいという等式制約を宣言します。 変数は $a$ が 236 個、$x$ が 225 個の計 461 個です。

このパズルには最小化したい目的関数がなく、すべての制約を満たすとエネルギーが $0$ になります。 search(target_energy=0) で、エネルギー $0$ の解が見つかった時点で探索を打ち切ります。 最後に、黒マスを #、白マスを . で表示します。

実行すると次の出力が得られ、猫の顔が現れます:

...............
.#...........#.
.##.........##.
.###.......###.
.#############.
.#############.
.##..#####..##.
.##..#####..##.
.#############.
.######.######.
.#####...#####.
..###########..
...#########...
.....#####.....
...............

この問題の解はこの 1 つだけです。