ピクロスのルール¶
ピクロスとは、以下のような長方形の盤面に対して、盤面の左と上に数字で与えられているヒントを元にいくつかのマスを黒く塗っていき、絵を完成させるパズルです。このサンプルコードでは、以下のようなサンプル問題を扱います。
各行の左に書かれているヒント数字は、その行において黒く塗られるマスがいくつ連続するかを表します。また、各列の上に書かれているヒント数字は、その列において黒く塗られるマスがいくつ連続するかを表します。
例えばヒントに 5 と書かれていた場合、その行または列の連続する5マスを黒く塗りつぶすことを表します。また、1 3
の場合は、1つのマスを黒く塗り、1つ以上の空白を挟んで、その右に連続する3つのマスを黒く塗る、という塗り方を表します。
サンプル問題の解は、以下のような「A」の形の絵になります。
ピクロスの定式化¶
定式化方針¶
ピクロスを Amplify AE などの組合せ最適化ソルバーを用いて解くためには、定式化に工夫が必要です。以下のような方針で定式化を進めることを考えます。
- いくつかのバイナリ変数 $q^\text{row}$ を用いて、行に関するヒント (盤面の左にあるヒント) を満たす盤面の塗り方を表現します。
- 別のいくつかのバイナリ変数 $q^\text{col}$ を用いて、列に関するヒント (盤面の上にあるヒント) を満たす盤面の塗り方を表現します。
- 上記で用意した 2 種類のバイナリ変数 $q^\text{row}$、$q^\text{col}$ に対し、それぞれが表現する盤面の塗り方が一致するような制約条件を課します。
以下の 2 つの図は、それぞれ行に関するヒントのみを満たす盤面・列に関するヒントのみを満たす盤面の例です。
次に、どのようにバイナリ変数を用いて盤面の塗り方を表現するかについて説明します。
行に関するヒントを満たす盤面の表現¶
行に関するヒントを満たす盤面を、以下の図のようにいくつかのマスに数字を対応付けることで表現します。
これは、盤面の各行において、連続する黒マスのうち最も左にあるマスに、左から順に $0, 1, \ldots$ の数字を書き込んでいったものです。
このとき、各行について、以下が成り立ちます。
ある行に関するヒントが $h_0, h_1, \ldots, h_{n-1}$ であるとき、
- その行には $0$ から $n-1$ までの数字がちょうど一回ずつ書かれている
- $0 \leq k < n-1$ に対し、数字 $k+1$ が書かれたマスは数字 $k$ が書かれたマスよりも $h_k + 1$ マス以上右にある
- 数字 $n-1$ が書かれたマスが、右から数えて $h_{n-1}$ マス目のマスより右にあることはない
たとえばある行に対するヒント数字が 2, 1, 2 であるとき、これらの性質を図示すると以下のようになります。
行に関する変数の用意¶
各マスに書き込まれている数字をバイナリ変数で表現します。1 マスにつき、(その行のヒント数字の数) 個のバイナリ変数を用意し、$i$ 番目の変数が 1 となっているとき、そのマスに $i$ が書かれていることを表現させます。たとえば上の図の 2 行目において、ヒント数字の個数は 2 個であり、 左から 2 番目のマスに 0 が、4 番目のマスに 1 が書かれています。これらは以下のように $5 \times 2$ 個のバイナリ変数テーブルを用いて表現できます。
| マス \ 数字 | 数字 0 | 数字 1 |
|---|---|---|
| 左から 1 番目のマス | 0 | 0 |
| 左から 2 番目のマス | 1 | 0 |
| 左から 3 番目のマス | 0 | 0 |
| 左から 4 番目のマス | 0 | 1 |
| 左から 5 番目のマス | 0 | 0 |
上の表で、たとえば左から 1 番目のマスに対応する 2 個の変数の値はともに 0 ですが、これはこのマスに数字が書かれていないことを表します。また、左から 2 番目のマスに対応する変数のうち、数字 0 が書かれてあることを表す変数が 1 であり、これはこのマスに 0 が書かれてあることを表現しています。
このように、各行ごとに (列の数) × (その行のヒント数字の数) 個のバイナリ変数を用意します。$i$ 行 $j$ 列のマスに数字 $k$ が書き込まれるかどうかを表すバイナリ変数を $q^\text{row}_{i,j,k}$ と表すことにします。
制約条件¶
次に、$q^\text{row}_{i,j,k}$ が、行に関するヒントをみたす盤面の表現となっているために必要な制約を課します。
まず、あるマスには 1 つの数字が書かれているか、数字が書かれていないかのいずれかである必要があります。これは、各マスに対して、そのマスに対応する (その行のヒント数字の数) 個のバイナリ変数のうち 0 個または 1 個が 1 であるということです。数式で表すと
$$ \sum_k q^\text{row}_{i,j,k} \leq 1 $$
となります。
次に、それぞれの行ごとに、ヒントがみたされているための条件を課します。
ある行に関するヒントが $h_0, h_1, \ldots, h_{n-1}$ であるとします。前述の通り、
- その行には $0$ から $n-1$ までの数字がちょうど一回ずつ書かれている
- $0 \leq k < n-1$ に対し、数字 $k+1$ が書かれたマスは数字 $k$ が書かれたマスよりも $h_k + 1$ マス以上右にある。
- 数字 $n-1$ が書かれたマスが、右から数えて $h_{n-1}$ マス目のマスより右にあることはない。
の 3 つが成り立つことが必要です。
まず、1 つ目の「その行には $0$ から $n-1$ までの数字がちょうど一回ずつ書かれている」は、バイナリ変数テーブルにおいては各列の和が 1 であることに対応します。各 $0 \leq k \leq n-1$ に対して、その行のあるマスに $k$ が書かれていることを表す変数のうち 1 つのみが 1 であればよいので、
$$ \sum_j q^\text{row}_{i,j,k} = 1 $$
と書くことができます。
次に、2 つ目の「$0 \leq k < n-1$ に対し、数字 $k+1$ が書かれたマスは数字 $k$ が書かれたマスよりも $h_k + 1$ マス以上右にある」という条件は、各行の最後以外のヒント数字に関する制約条件であり、「$j_2 - j_1 < h_k+1$ のとき、列番号が $j_1$ のマスに数字 $k$ が、列番号が $j_2$ のマスに数字 $k+1$ が書かれていることはない」と言い換えられます。すると
$$ q^\text{row}_{i,j_1,k} q^\text{row}_{i, j_2, k+1} = 0 \quad (j_2 - j_1 < h_k + 1,\ \text{$h_k$ は $i$ 行目の $k$ 番目のヒント数字}) $$
と書くことができます。
最後に、3 つ目の「数字 $n-1$ が書かれたマスが、右から数えて $h_{n-1}$ マス目のマスより右にあることはない」という条件は、各行の最後のヒント数字に関する制約であり、
$$ q^\text{row}_{i, j, n-1} = 0 \quad (j > (\text{列の数}) - h_{n-1}) $$
と書くことができます。
逆に、以上の条件を満たしているならば、$q^\text{row}$ は行に関するヒントをみたす盤面の表現となります。
列に関するヒントを満たす盤面の表現¶
列に関するヒントについても、$q^\text{row}$ と同様に、列ごとに (行の数) × (ヒントの数) 個のバイナリ変数 $q^\text{col}$ を定義することにより、表現できます。
列に関するヒントを満たす盤面は、たとえば上に挙げた例に対しては、以下のように盤面に数字を書き込むことで表されます。
$i$ 行 $j$ 列目のマスに数字 $k$ が書かれていることを表す変数を $q^\text{col}_{j, i, k}$ で表します。列インデックス $j$ が最初の添え字となっていることに注意してください。
$q^\text{col}$ に対しても、$q^\text{row}$ と同様にして、列に関するヒントを満たす盤面を表現するための制約条件を導入することができます。前項までの「行」を「列」に、「左」を「上」に読み替えてください。
盤面が一致するための制約条件¶
このようにして用意した 2 種類のバイナリ変数 $q^\text{row}$、$q^\text{col}$ に対し、それぞれが表現する盤面の塗り方が一致するような制約条件を課します。
まず、$q^\text{row}$ の値から盤面を復元することを考えます。
たとえば、ある行のヒント数字が 2 1 2 であるとき、あるマスが黒く塗られるための条件は、以下のいずれかを満たすことです。
- 数字 0 が、そのマスあるいはひとつ左のマスに書かれている
- 数字 1 が、そのマスに書かれている
- 数字 2 が、そのマスあるいはひとつ左のマスに書かれている
$q^\text{row}$ に課した制約条件により、これらの条件が 2 つ以上満たされることはありえないので、$i$ 行目のヒント数字が $2 1 2$ であるとき、$i$ 行 $j$ 列のマスの色は、$q^\text{row}$ を用いた以下の数式の値が 1 であれば黒、0 であれば白となります。
$$ q^\text{row}_{i, j, 0} + q^\text{row}_{i, j-1, 0} + q^\text{row}_{i, j, 1} + q^\text{row}_{i, j, 0} + q^\text{row}_{i, j-1, 0} $$
ヒント数字が別の値である場合も同様にして、盤面の各マスの色を $q^\text{row}$ の 1 次式により表すことができます。一般的には、$i$ 行 $j$ 列のマスの色は、$i$ 行のヒント数字を $h_0, h_1, \ldots$ として、
$$ C^\text{row}_{i,j} = \displaystyle\sum_k \sum_{r=j-h_k+1}^j q^\text{row}_{i,r,k} $$
の値が 1 ならば黒であり、0 ならば白となります。
同様にして、$q^\text{col}$ の値から盤面を復元できます。$i$ 行 $j$ 列のマスの色は、$j$ 列のヒント数字を $H_0, H_1, \ldots$ として、
$$ C^\text{col}_{i,j} = \displaystyle\sum_k \sum_{r=i-H_k+1}^j q^\text{col}_{j,r,k} $$
の値が 1 ならば黒であり、0 ならば白です。
したがって、$i$ 行 $j$ 列のマスについて、$i$ 行目のヒント数字が $h_0, h_1, \ldots$ で $j$ 列目のヒント数字が $H_0, H_1, \ldots$ であるとき、$C^\text{row}_{i,j} = C^\text{col}_{i,j}$、すなわち
$$ \sum_k \sum_{r=j-h_k+1}^j q^\text{row}_{i,r,k} = \sum_k \sum_{r=i-H_k+1}^j q^\text{col}_{j,r,k} $$
という制約条件を課すことで、$q^\text{row}$ および $q^\text{col}$ からそれぞれ復元した盤面を一致させることができます。
以上により、ピクロスの定式化が完成しました。
ピクロスの求解¶
それでは、上記で解説した定式化をもとに、ピクロスの解法を Amplify を使って実装しましょう。
ピクロスの可視化関数¶
実装に入る前に、ピクロスの盤面及び解を表示するための関数 plot_picross を定義します。
import matplotlib.pyplot as plt
import numpy as np
def plot_picross(row_hints: list, col_hints: list, solution: np.ndarray | None = None):
num_rows = len(row_hints)
num_cols = len(col_hints)
if solution is None:
solution = np.zeros((num_rows, num_cols))
_, ax = plt.subplots()
ax.tick_params(
which="both",
top=True,
bottom=False,
labeltop=True,
labelbottom=False,
length=0,
)
ax.tick_params(axis="x")
ax.imshow(solution, cmap="Greys", aspect="equal")
# 主目盛り
ax.set_xticks(np.arange(num_cols))
ax.set_yticks(np.arange(num_rows))
# 副目盛り
ax.set_xticks(np.arange(-0.5, num_cols, 1), minor=True)
ax.set_yticks(np.arange(-0.5, num_rows, 1), minor=True)
# 主目盛りのラベル
ax.set_xticklabels(["\n".join(map(str, hint)) for hint in col_hints])
ax.set_yticklabels([" ".join(map(str, hint)) for hint in row_hints])
ax.set_xlim((-0.5, num_cols - 0.5))
ax.set_ylim(num_rows - 0.5, -0.5)
ax.set_title(f"{num_rows} x {num_cols}", fontsize=20, pad=20)
# 副目盛りに基づく格子
ax.grid(which="minor", color="#aaaaaa", linestyle="-", linewidth=1)
plt.show()
また、定義した plot_picross 関数を用いて、ピクロスのルール
で紹介したピクロスパズルと同じ問題を作成し、描画します。
# ヒントをリストで表記
row_hints = [[1], [1, 1], [1, 1], [5], [1, 1]] # 行に関するヒント
col_hints = [[2], [3], [1, 1], [3], [2]] # 列に関するヒント
# 盤面のサイズを定義
num_rows = len(row_hints)
num_cols = len(col_hints)
# ピクロス問題をプロット
plot_picross(row_hints, col_hints)
決定変数の定義¶
定式化の実装に移ります。まず、必要な決定変数を Amplify の VariableGenerator を用いて発行します。
行に関するヒントを満たす盤面を作成するための変数 $q^\text{row}$ は、行ごとに (列の数) $\times$ (ヒント数字の個数) の形の 2 次元バイナリ変数配列
q_row を発行します。q_row[i] は 2 次元配列であり、q_row[i][j, k] は
i 行
j 列のマス目に数字 k が書き込まれるかどうかを表します。
同様に、列に関するヒントを満たす盤面を作成するための変数 $q^\text{col}$ は、列ごとに (行の数) $\times$ (ヒント数字の個数) の 2 次元バイナリ変数配列
q_col を発行します。q_col[j] は 2 次元配列であり、q_col[j][i, k] は
i 行
j 列のマス目に数字 k が書き込まれるかどうかを表します。
from amplify import VariableGenerator
gen = VariableGenerator()
# 変数の発行
q_row = [
gen.array("Binary", shape=(num_cols, len(hint)), name=f"qrow^{i}")
for i, hint in enumerate(row_hints)
]
q_col = [
gen.array("Binary", shape=(num_rows, len(hint)), name=f"qcol^{j}")
for j, hint in enumerate(col_hints)
]
たとえば、上から 2 行目 (i=1) に対応する $q^\text{row}_{i=1,j,k}$ の変数は以下のように表示できます。
q_row[1]
q_row に対する制約条件の実装¶
q_row が行に関するヒントをみたす盤面を表すための制約条件を課します。以下を表す制約条件を作成する必要があります。
- あるマスには 1 つの数字が書かれているか、数字が書かれていないかのいずれかである
さらに、ある行のヒント数字が $h_0, \ldots, h_{n-1}$ であるとき、
- その行には $0$ から $n-1$ までの数字がちょうど一回ずつ書かれている
- $0 \leq k < n-1$ に対し、数字 $k+1$ が書かれたマスは数字 $k$ が書かれたマスよりも $h_k + 1$ マス以上右にある。
- 数字 $n-1$ が書かれたマスが、右から数えて $h_{n-1}$ マス目のマスより右にあることはない。
まず、最後の「数字 $n-1$ が書かれたマスが、右から数えて $h_{n-1}$ マス目のマスより右にあることはない」という制約を課します。これは数式では
$$ q^\text{row}_{i, j, n-1} = 0 \quad (j > (\text{列の数}) - h_{n-1}) $$
と表すことができ、コード上では変数配列への値の代入により実装できます。変数配列への値の代入は、他の目的関数や制約条件の構築よりも前に行う必要があります。
for i, hint in enumerate(row_hints):
if len(hint) > 0:
q_row[i][num_cols - hint[-1] + 1 :, len(hint) - 1] = 0
上から 4 列目 (i=3) に対応する q_row の値を表示してみます。一番左の列 (j=0) 以外の列には、数字 0
は書き込まれないことが分かります。
q_row[3]
次に、1 つ目の制約「あるマスには 1 つの数字が書かれているか、数字が書かれていないかのいずれかである」を作成します。これは数式で表すと
$$ \sum_k q^\text{row}_{i,j,k} \leq 1 $$
です。2 次元配列 q_row の $k$ (axis=1) に関する和を取るので、less_equal 関数に
axis=1 を与えます。
from amplify import less_equal, sum as amplify_sum
row_constraints1 = amplify_sum(less_equal(q_row[i], 1, axis=1) for i in range(num_rows))
「ある行のヒント数字が $h_0, \ldots, h_{n-1}$ であるとき、その行には $0$ から $n-1$ までの数字がちょうど一回ずつ書かれている」という制約を作成します。これは数式で表すと
$$ \sum_j q^\text{row}_{i,j,k} = 1 $$
です。2 次元配列 q_row[i] の $j$ (axis=0) に関する和を取るので、one_hot 関数に
axis=0 を与えます。
from amplify import one_hot
row_constraints2 = amplify_sum(one_hot(q_row[i], axis=0) for i in range(num_rows))
「ある行のヒント数字が $h_0, \ldots, h_{n-1}$ であるとき、$0 \leq k < n-1$ に対し、数字 $k+1$ が書かれたマスは数字 $k$ が書かれたマスよりも $h_k + 1$ マス以上右にある」という制約を作成します。これは数式で表すと
$$ q^\text{row}_{i,j_1,k} q^\text{row}_{i, j_2, k+1} = 0 \quad (j_2 - j_1 < h_k + 1) $$
となります。
まず、$i$, $j_1$, $k$ を固定して、$j_2 - j_1 < h_k + 1$ を満たす $j_2$ すべてについて $q^\text{row}_{i,j_1,k}
q^\text{row}_{i, j_2, k+1}$ を集めた 1 次元配列を作成します。次に、equal_to 関数を用いて、この配列の要素がすべて 0
と等しくなるような制約条件を一括で生成します。配列の各要素についての制約を一括生成するには、axis パラメータに空のタプルを指定します。
from amplify import ConstraintList, equal_to
row_constraints3 = ConstraintList()
for i, hint in enumerate(row_hints):
for j1 in range(num_cols):
for k, hint_num in enumerate(hint[:-1]):
lhs_list = q_row[i][j1, k] * q_row[i][: j1 + hint_num + 1, k + 1]
row_constraints3 += equal_to(lhs_list, 0, axis=())
以上により、q_row に関する制約条件を作成できました。これらをひとつの制約条件リストにまとめておきます。
row_constraints = row_constraints1 + row_constraints2 + row_constraints3
q_col に対する制約条件の実装¶
q_col に対しても、q_row と同様に制約を課します。
for j, hint in enumerate(col_hints):
if len(hint) > 0:
q_col[j][num_rows - hint[-1] + 1 :, len(hint) - 1] = 0
col_constraints1 = amplify_sum(less_equal(q_col[j], 1, axis=1) for j in range(num_cols))
col_constraints2 = amplify_sum(one_hot(q_col[j], axis=0) for j in range(num_cols))
col_constraints3 = ConstraintList()
for j, hint in enumerate(col_hints):
for i1 in range(num_rows):
for k, hint_num in enumerate(hint[:-1]):
lhs_list = q_col[j][i1, k] * q_col[j][: i1 + hint_num + 1, k + 1]
col_constraints3 += equal_to(lhs_list, 0, axis=())
col_constraints = col_constraints1 + col_constraints2 + col_constraints3
一致制約の実装¶
2 種類のバイナリ変数 q_row、q_col がそれぞれ表す盤面が一致する制約を実装します。まず、q_row
から盤面を復元したときの各マスの色を表す配列を作成します。$i$ 行 $j$ 列のマスの色は、$i$ 行のヒント数字を $h_0, h_1, \ldots$ として、
$$ \sum_k \sum_{r=j-h_k+1}^j q^\text{row}_{i,r,k} $$
により表現できます。
from amplify import PolyArray
field_from_q_row = PolyArray(np.zeros((num_rows, num_cols)))
for i, hint in enumerate(row_hints):
for j in range(num_cols):
for k, hint_num in enumerate(hint):
field_from_q_row[i, j] += q_row[i][
max(j - hint_num + 1, 0) : j + 1, k
].sum()
同様に、q_col から盤面を復元したときの各マスの色を表す配列を作成します。
field_from_q_col = PolyArray(np.zeros((num_rows, num_cols)))
for j, hint in enumerate(col_hints):
for i in range(num_rows):
for k, hint_num in enumerate(hint):
field_from_q_col[i, j] += q_col[j][
max(i - hint_num + 1, 0) : i + 1, k
].sum()
equal_to 関数を用いて、q_row、q_col
からそれぞれ復元した盤面の各マスの色が一致する制約条件を作成します。配列の各要素に対して一括で制約条件を作成するには、axis パラメータに空のタプルを指定します。
field_equal_constraints = equal_to(field_from_q_row - field_from_q_col, 0, axis=())
組合せ最適化モデルの構築¶
これまでに作成した制約条件をすべてまとめて、組合せ最適化モデルを構築します。
from amplify import Model
model = Model(row_constraints + col_constraints + field_equal_constraints)
from amplify import FixstarsClient
from datetime import timedelta
client = FixstarsClient()
client.parameters.timeout = timedelta(seconds=1) # タイムアウト1秒
# client.token = "API トークンを入力してください"
Amplify AE を用いて求解を実行します。
from amplify import solve
result = solve(model, client)
if len(result) == 0:
raise RuntimeError("no feasible solution found")
配列 field_from_q_row に解を代入することで、解の値から盤面の色を復元することができます。
solution = field_from_q_row.evaluate(result.best.values)
最後に、結果を表示します。
plot_picross(row_hints, col_hints, solution)
以上により、ピクロスの問題を解くことができました。
