動画：ノノグラム（Python）
動画「QUBO++ ケーススタディ ノノグラム（Python）」の手引きです。 章ごとに、要点と動画に出てくるプログラム・出力、詳しい説明のページへのリンクをまとめています。 「▶ 動画の … から再生」をクリックすると、その場面から再生します。 動画では一部ずつ見せているプログラムも、ここではそのまま実行できる形で載せています。
この動画で扱うこと：
- ノノグラムのルールと、15 × 15 の問題（答えは QUBO++ のロゴ）
- 塊の位置を、左寄せからの移動量で表し、移動量をドメインウォールの変数で表す
- 塊の並びの条件を 2 次のペナルティ項に、塊がマスを覆う条件を帯の 2 か所の値の差にして、マスの色を線形式で表す
- 行から見た色と列から見た色が等しいという等式を
qbpp.cons()で宣言して解き、展開して QUBO としても解く
文章での説明はノノグラムのページにあります。動画（ケーススタディ）の一覧に戻る
ルール
盤面の左と上の数字は、その行（列）の黒マスの塊の長さを、左から（上から）順に並べたものです。 塊と塊の間には白マスが 1 個以上入り、その数や両端の白マスの数は手がかりには書かれていません。 今回の問題は 15 行 15 列で、どの行・列にも黒マスがあります。答えは 1 つだけです。
塊の移動量
例として、問題の 5 行目（手がかり 3 1 1 3、長さ 15、塊は 4 個）を使います。
- すべての塊を左に寄せると、塊 0〜3 の開始位置は $e = 0, 4, 6, 8$ で、右に $d = 4$ マスの余白が残ります。
- 各塊を左寄せから右にずらした量を移動量 $t$ と呼びます。答えの配置では $t = (0, 1, 3, 4)$ です。
- 移動量は 0 以上 $d$ 以下で、塊は追い越せないので、後ろの塊ほど移動量は大きいか等しくなります。
j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
# # # . # . # . # # # . . . . t = (0, 0, 0, 0) 左寄せ
# # # . . # . . . # . . # # # t = (0, 1, 3, 4) 答え
. . . . # # # . # . # . # # # t = (4, 4, 4, 4) 右寄せ
ドメインウォール
$d$ 個のバイナリ変数を、1 がすべて 0 より前に並ぶ形（$1\cdots 1\,0\cdots 0$）に限り、1 と 0 の境目を壁と見なします。 壁の前の 1 の個数で 0 以上 $d$ 以下の整数を表します（$d = 4$ なら 0000〜1111 の 5 通りで 0〜4、1110 は 3）。
- 1 つの変数を反転して壁をずらすと、表す整数が 1 だけ増減します。
- 1 の個数だけで表す方法と違い、表し方は 1 通りなので、$p$ 番目の変数を見るだけで「整数が $p$ より大きいか」が分かります。
移動量をドメインウォールで
塊 $k$ の移動量を 4 個の変数 y[k, p]（$p = 0, \ldots, 3$）で表します。y[k, p] が 1 なのは、移動量が $p$ より大きいときです。 答えの移動量 0, 1, 3, 4 を、塊を行、$p$ を列とする表に並べると次のとおりです。
| $p=0$ | $p=1$ | $p=2$ | $p=3$ | |
|---|---|---|---|---|
| 塊 0（$t=0$） | 0 | 0 | 0 | 0 |
| 塊 1（$t=1$） | 1 | 0 | 0 | 0 |
| 塊 2（$t=3$） | 1 | 1 | 1 | 0 |
| 塊 3（$t=4$） | 1 | 1 | 1 | 1 |
- 各行はドメインウォール（0 の右に 1 が来ない）。崩れると
~y[k, p] * y[k, p + 1]が 1 になります。 - 各列を上から読むと逆向きのドメインウォール（1 の下に 0 が来ない）。崩れると
y[k, p] * ~y[k + 1, p]が 1 になります。 - どちらの積も形が崩れた所でだけ 1 になるので、そのままペナルティ項にでき、塊の並びの条件は補助変数なしの 2 次の項で書けます。
塊がマスを覆う条件
1 つの塊と 1 つのマス
塊 3（長さ $r = 3$、開始位置 $e = 8$）を右にずらしながら、11 の位置のマスを見ます。
| 移動量 $t$ | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 塊 3 の位置 | 8〜10 | 9〜11 | 10〜12 | 11〜13 | 12〜14 |
| 11 を覆うか | × | ○ | ○ | ○ | × |
一般に、塊は位置 $e+t$ から $r$ マスを覆うので、位置 $j$ を覆うのは $j-e-r < t \leq j-e$ のときです。 この例では $0 < t \leq 3$、つまり移動量 1, 2, 3 のときです。
帯と壁で見る
移動量が $q$ より大きければ 1、そうでなければ 0 の値を $Y(q)$ とします。
- $q$ を増やすと $Y(q)$ は 1 が続き、$q$ が移動量に達すると 0 になります。$Y$ を並べた帯は、壁の位置が移動量のドメインウォールです。
- $0 \leq q \leq d-1$ では $Y(q)$ は変数
y[k, q]そのもの、$q < 0$ では 1、$q \geq d$ では 0（定数）です。
帯の上に目印 $a = j-e-r$ と $b = j-e$ を立てると、塊がマスを覆うのは、壁が $a$ と $b$ の間にあるときです。
| 壁の位置 | $Y(a)$ | $Y(b)$ | $Y(a)-Y(b)$ |
|---|---|---|---|
| $a$ と $b$ の間 | 1 | 0 | 1 |
| $a$ より左 | 0 | 0 | 0 |
| $b$ より右 | 1 | 1 | 0 |
| （ありえない） | 0 | 1 |
帯は 1 の後に 0 しか来ないので、最後の行は起きません。したがって、塊が覆う ⇔ $Y(a)-Y(b)=1$ です。
例で確かめる
答えの移動量 $(0, 1, 3, 4)$ で確かめます。
- 5 の位置：塊 1（長さ 1、開始位置 4）は $a=0$、$b=1$。帯は 1000 なので $Y(0)-Y(1)=1-0=1$。塊 1 が覆うので黒です。
- 3 の位置：塊 0 は $a=0$、$b=3$ で帯は 0000、差は 0。塊 1〜3 は $a$ も $b$ も負で、帯の外の 1 どうしなので差は 0。どの塊も覆わないので白です。
塊ごとの差を足したものが、行から見たマスの色です。塊は重ならないので和は 0 か 1 です。 $Y$ は変数か定数なので、マスの色は変数の線形式になります（5 の位置なら y[0, 2] + y[1, 0] - y[1, 1]）。 移動量を整数変数で表すと、「$q$ より大きいか」を式で書けないので、このようには書けません。
詳しくはノノグラムの「行から見たマスの色」をご覧ください。
列と行の一致
列も同じように、上に寄せた位置から下への移動量を、ドメインウォールの変数 z で表します。 列から見たマスの色も z の線形式です。 すべてのマスで「行から見た色 − 列から見た色 = 0」という等式を制約にします（225 マスで 225 本）。 補助変数はなく、変数は y 198 個と z 239 個の 437 個です。目的関数はなく、すべての条件を満たせばエネルギーは 0 です。
プログラム
手がかりと 3 つの関数
- 手がかりはリストのリストで、
ROWS[i]が行 $i$、COLS[j]が列 $j$ の手がかりです。 line_varは 1 本の行（列）のドメインウォールの変数（塊の数 × 余白の 2 次元配列、さきほどの表）を作ります。movedは帯の値 $Y(q)$ を返します（$q$ が負なら 1、$d$ 以上なら 0、それ以外は変数）。blackは、開始位置eを進めながら、塊ごとに $a$ でのmovedから $b$ でのmovedを引いた差をリストに集め、qbpp.sum()で足して、行から見たマスの色を返します。
並びの条件と解き方
line_consの 1 つ目のループが行の形、2 つ目のループが列の形のペナルティ項を足します。yは行ごと、zは列ごとの変数配列のリストです（塊の数と余白が行ごとに違うため）。fに並びの条件を足し、すべてのマスで 2 つの色の差が 0 という制約をqbpp.cons()で足します。- 否定を含む項を足したので
simplify_as_binary()で整理し、EasySolverでtarget_energy=0を指定して解きます。
import pyqbpp as qbpp
# 手がかり: ROWS[i][k] は行 i の k 番目の塊の長さ、COLS[j][k] は列 j の k 番目の塊の長さ。
ROWS = [[7], [11], [4, 4], [2, 2], [3, 1, 1, 3], [2, 3, 3, 2], [2, 1, 1, 2], [2, 2],
[3, 3], [2, 2], [4, 4], [10], [7, 2], [4], [3]]
COLS = [[5], [9], [4, 4], [2, 2], [3, 1, 3], [2, 3, 2], [2, 1, 2], [2, 2],
[2, 1, 2], [2, 3, 2], [3, 1, 3], [2, 2, 1], [4, 3, 3], [9, 3], [5, 2]]
H, W = len(ROWS), len(COLS)
# 長さ n の行 (列) のドメインウォール w[k, p]: 塊 k の移動量を表す。
def line_var(name, clue, n):
d = n - sum(clue) - len(clue) + 1 # 余白
return qbpp.var(name, shape=(len(clue), d))
# 塊 k の移動量が q より大きければ 1 になる式。
def moved(w, k, q):
if q < 0:
return 1
if q >= w.shape[1]:
return 0
return w[k, q]
# 位置 j が黒なら 1 になる式。
def black(w, clue, j):
b = []
e = 0 # 塊 k の左寄せ (上寄せ) の開始位置
for k in range(len(clue)):
b.append(moved(w, k, j - e - clue[k]) - moved(w, k, j - e))
e += clue[k] + 1
return qbpp.sum(b)
# 1 本の行 (列) の制約。
def line_cons(w):
m, d = w.shape
g = 0
for k in range(m):
for p in range(d - 1):
g += ~w[k, p] * w[k, p + 1] # ドメインウォールの形 (0 の次に 1 なら 1)
for k in range(m - 1):
for p in range(d):
g += w[k, p] * ~w[k + 1, p] # 塊の順序 (1 の下に 0 なら 1)
return g
y = [line_var(f"y{i}", ROWS[i], W) for i in range(H)] # 行 i のドメインウォール
z = [line_var(f"z{j}", COLS[j], H) for j in range(W)] # 列 j のドメインウォール
f = 0
for w in y + z:
f += line_cons(w)
for i in range(H):
for j in range(W):
f += qbpp.cons(black(y[i], ROWS[i], j) - black(z[j], COLS[j], i) == 0) # 行と列の色の一致
f.simplify_as_binary()
sol = qbpp.EasySolver(f).search(target_energy=0)
for i in range(H):
print("".join("#" if sol(black(y[i], ROWS[i], j)) else "." for j in range(W)))
実行例
出力の # と . を盤面に重ねると、QUBO++ のロゴが現れます。答えは 1 つなので、何度実行しても同じ出力です。
....#######....
..###########..
.####.....####.
.##.........##.
###..#...#..###
##..###.###..##
##...#...#...##
##...........##
###.........###
.##.........##.
.####.....####.
..##########...
....#######.##.
...........####
............###
QUBOとして解く
qbpp.expand_cons() で、qbpp.cons() の制約をペナルティ式に展開します。 等式は (行から見た色 − 列から見た色)² になり、どちらの色も線形式なので 2 次式です。並びの条件はもともと 2 次のペナルティ項です。 展開した式は補助変数のない QUBO で、エネルギーが 0 になるのはすべての条件を満たすときだけです。 上のプログラムの最後に次の行を足します。
g = qbpp.expand_cons(f)
g.simplify_as_binary()
sol = qbpp.EasySolver(g).search(target_energy=0)
print(f"var_count = {sol.info['var_count']}, term_count = {sol.info['term_count']}")
出力：
var_count = 437, term_count = 2756
変数は 437 個のままで、項は 2756 個です。QUBO を受け付けるほかのソルバーにも、この形で渡せます。
詳しくはノノグラムの「QUBO として解く」をご覧ください。
まとめ
- 塊の位置を左寄せからの移動量で表し、移動量をドメインウォールの変数で表しました。
- 塊の並びの条件は 2 次のペナルティ項になりました。
- 塊がマスを覆う条件は帯の 2 か所の値の差で書けるので、マスの色は変数の線形式になりました。
- 行から見た色と列から見た色が等しいという等式で行と列を結び、補助変数なしで解けます。展開すればそのまま QUBO です。