組合せ最適化でボンバーパズルを解く

Advent Calendar 2日目の記事 組合せ最適化でカックロを解く
Advent Calendar 4日目の記事 組合せ最適化でエデンの園配置を証明する

これなに

ボンバーパズルを、Pythonで組合せ最適化モデルを作って解きます。
解く楽しみは、モデル化を工夫することになります。

自分でも試してみたい人は、下記を参考にしてください。

• 数独を通して組合せ最適化を学ぼう

問題

下図の白いマスに爆弾が隠れています（下図は答えなので爆弾（●）が見えています）。
数字はヒントで、周囲9マスの爆弾の数になります。数字のマスに爆弾が入ることはありません。

dataにヒントの数字が入っているとします。

python

import numpy as np, matplotlib.pyplot as plt
from pulp import LpProblem, lpSum, value
from ortoolpy import addbinvars
data = """\
12..1
..3.1
.4.3.
..4.2
22..2""".splitlines()

変数表

下記のような変数表を作成します。各行の変数は0または1をとります。
変数の値が1ならば、該当行 該当列のマスに爆弾があります。
「字」はdataの値です。「.」でないならば、爆弾はないので、Varに0を代入します。

	行	列	字	Var
0	0	0	1	0
1	0	1	2	0
...	...	...	...	...

python

ni,nj = len(data),len(data[0])
a = pd.DataFrame([(i,j,data[i][j]) for i in range(ni)
    for j in range(nj)], columns=list('行列字'))
a['Var'] = addbinvars(len(a))
a.loc[a.字!='.','Var'] = 0
a[:2]

数理モデルを作り解く

変数表ができたので、ボンバーパズルの解になるように、制約条件を追加し数理モデルを作成し、解きましょう。

• 周囲9マスの爆弾の合計を数字の通りに。 …(1)
  • 周囲9マスは、DataFrame.queryで簡単に取り出せます。

python

m = LpProblem()
for i in range(ni):
    for j in range(nj):
        if data[i][j].isdigit():
            q = f'{i-1}<=行<={i+1}&{j-1}<=列<={j+1}'
            m += lpSum(a.query(q).Var) == int(data[i][j]) # (1)
m.solve()

結果の表示

python

a['Val'] = a.Var.apply(value)
a.loc[a.Val>0.5,'字'] = '●'
print('\n'.join(' '.join(c) for c in a.字.values.reshape(ni,nj)))
>>>
1 2 ● . 1
● . 3 ● 1
. 4 ● 3 .
● ● 4 ● 2
2 2 . ● 2

解けていることが確認できます。

以上