Advent Calendar 7日目の記事組合せ最適化で因子の部屋を解く
Advent Calendar 9日目の記事組合せ最適化でチョコナを解く

これなに

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

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

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

問題

盤面のいくつかのマスを黒くぬります。
黒マスは必ずタテかヨコにちょうど２つだけぬります。
太線で区切られた各部分には、黒マスが２つずつ入ります。

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

Pythonでは、data（部屋のグループ）を使うことにします。

python

import pandas as pd, matplotlib.pyplot as plt
from pulp import LpProblem, lpSum, value
from ortoolpy import addbinvars
data = """\
ABBBC
ADDBC
EDBBB
EEEEE
EEEEE""".splitlines()

変数表

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

	行	列	字	Var
0	0	0	A	v000001
1	0	1	B	v000002
...	...	...	...	...

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[:2]

数理モデルを作り解く

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

あるマスが黒なら、その上下左右の黒の数はちょうど1となる。これは、下記の2つの式で表現できます（Mは十分大きな数）。
- 上下左右の黒の数 >= 該当マスの黒の数
- 上下左右の黒の数 <= 1 + M*(1-該当マスの黒の数)
各グループ内の黒の数はちょうど2。

python

m = LpProblem()
for _,r in a.iterrows():
    e = lpSum(a.query(f'abs(行-{r.行})+abs(列-{r.列})==1').Var)
    m += e >= r.Var
    m += e <= 1+(len(e)-1)*(1-r.Var)
for g,v in a.groupby('字'):
    m += lpSum(v.Var) == 2
m.solve()

結果の表示

python

a['Val'] = a.Var.apply(value)
plt.imshow((a.Val<0.5).values.reshape(ni,nj), cmap='gray', interpolation='none')
plt.show()

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

以上