組合せ最適化でスターバトルを解く

Advent Calendar 10日目の記事 組合せ最適化でクリークを解く
Advent Calendar 12日目の記事 組合せ最適化で推理パズルを解く

これなに

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

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

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

問題

• 各行、各列、各エリアに★をちょうど1つ置く。
• ★の周り(8か所)に★は置けない。

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

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

python

import pandas as pd, matplotlib.pyplot as plt
from pulp import LpProblem, lpSum, value
from ortoolpy import addbinvars
data = """\
AABBB
AABCC
ADDDC
DDECC
EEEEC""".splitlines()

変数表

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

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

python

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

数理モデルを作り解く

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

• 各行、各列、各エリアに★をちょうど1つ置く。
  • ['行','列','字']ごとに、groupbyして、和を1にします。
• ★の周り(8か所)に★は置けない。
  • 2x2マスの中に、★を1つ以下にすればOKです。

python

m = LpProblem()
for cl in ['行','列','字']:
    for _,v in a.groupby(cl):
        m += lpSum(v.Var) == 1
for i in range(nn-1):
    for j in range(nn-1):
        q = f'{i}<=行<={i+1}&{j}<=列<={j+1}'
        m += lpSum(a.query(q).Var) <= 1
m.solve()

結果の表示

python

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

別解ですが、制約条件は、満たしているようです。

以上