組合せ最適化でクリークを解く

Advent Calendar 9日目の記事 組合せ最適化でチョコナを解く
Advent Calendar 11日目の記事 組合せ最適化でスターバトルを解く

これなに

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

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

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

問題

• いくつかのマスを黒くぬります。
• 数字は、数字が隣接するマス中の黒マスの数を表します。
• すべての白マスは連結すること。

左が問題で、右が答えです。

Pythonでは、data（数字ならばヒント）を使うことにします。

python

import pandas as pd, matplotlib.pyplot as plt
from pulp import LpProblem, lpSum, value
from ortoolpy import addbinvars, unionfind
data = """\
....1.
0.....
..3.4.
.2.12.
...1.1
......""".splitlines()

変数表

下記のような変数表を作成します。各行の変数(Var)は0または1をとります。
変数の値が1ならば、該当行 該当列のマスが該当の数になります。

	行	列	Var
0	0	0	v000001
1	0	1	v000002
...	...	...	...

python

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

数理モデルを作り解く

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

• 数字のヒントは、周りの黒の数。
• 白が連結していること。
  • 制約条件として書くこともできますが、大変なので、ここでは一旦無視して解きます。
  • 答えが連結していないときに、その答えを禁止して解き直します。
  • 連結しているかどうかは、unionfind.isconnectedでできます。

python

m = LpProblem()
m += lpSum(a.Var)
for i in range(ni+1):
    for j in range(nj+1):
        if data[i][j].isdigit():
            q = f'{i-1}<=行<={i}&{j-1}<=列<={j}'
            m += lpSum(a.query(q).Var) == int(data[i][j])
while True:
    m.solve()
    r = a.Var.apply(value)
    if unionfind.isconnected((r!=1).values.reshape(ni,nj)):
        break
    m += lpSum(a[r==1].Var) <= (r==1).sum()-1

結果の表示

python

plt.imshow((1-r).values.reshape(ni,nj), cmap='gray', interpolation='none')
plt.show()

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

以上