Advent Calendar 20日目の記事 組合せ最適化でビルディングを解く
Advent Calendar 22日目の記事 組合せ最適化で不等式を解く
これなに
ひとりにしてくれを、Pythonで組合せ最適化モデルを作って解きます。
解く楽しみは、モデル化を工夫することになります。
自分でも試してみたい人は、下記を参考にしてください。
問題
- 盤面に並んでいる数字のうちいくつかを黒くぬり、タテでもヨコでも同じ列に同じ数字が複数個入らないようにします
- 黒マスをタテヨコに連続したり、黒マスで盤面を分断してはいけません
入力パラメータ
dataにヒントが入っているとします。
python
import numpy as np
from itertools import chain, product
from pulp import LpProblem, lpSum, value
from ortoolpy import addbinvars, unionfind
data = np.array([list(s) for s in """\
18626753
31118222
83247651
37583314
54467182
71432535
22834475
22314465""".splitlines()]).astype(int)
nn = len(data)
Pythonで解く
数理モデルを作成し、解きましょう。
変数
- v：0:number, 1:black (1)
制約
- 黒以外の数字は縦横に重複しないこと (2)
- 黒は連続しないこと (3)
- 黒で分断しないこと (4)
python
m = LpProblem()
v = np.array(addbinvars(nn, nn)) # 0:number, 1:black (1)
for i, j in product(range(nn), range(nn)):
for x in [v[i,:][data[i,:] == j+1], v[:,i][data[:,i] == j+1]]:
m += lpSum(x) >= len(x)-1 # (2)
for e in chain((v[1:,:] + v[:-1,:]).flat, (v[:,1:] + v[:,:-1]).flat):
m += e <= 1 # (3)
while True:
m.solve()
r = np.vectorize(value)(v)
if unionfind.isconnected(1-r):
break
m += lpSum(v[r==1]) <= r.sum() - 1 # (4)
結果の表示
python
data[r==1] = 0
print(data)
>>>
[[1 8 0 2 6 7 5 3]
[3 0 1 0 8 0 2 0]
[8 3 2 4 7 6 0 1]
[0 7 5 8 3 0 1 4]
[5 4 0 6 0 1 8 2]
[7 1 4 0 2 5 3 0]
[2 0 8 3 4 0 7 5]
[0 2 3 1 0 4 6 0]]
解けていることが確認できます。
以上