Advent Calendar 23日目の記事 組合せ最適化で波及効果を解く
Advent Calendar 25日目の記事 組合せ最適化でオーノーを解く
これなに
へやわけを、Pythonで組合せ最適化モデルを作って解きます。
解く楽しみは、モデル化を工夫することになります。
自分でも試してみたい人は、下記を参考にしてください。
問題
- 盤面のいくつかのマスを黒くぬります
- 太線で区切られた四角（部屋）に入っている数字は、その部屋に入る黒マスの数を表します
- 数字の入っていない部屋は、いくつ黒マスが入るか不明です
- 白マスを、タテまたはヨコにまっすぐに３つ以上の部屋にわたって続けさせてはいけません
- 黒マスをタテヨコに連続させたり、黒マスで盤面を分断したりしてはいけません
入力パラメータ
dataにヒントが入っているとします。
python
import numpy as np
from collections import defaultdict
from itertools import chain, groupby, product
from pulp import LpProblem, lpSum, value
from ortoolpy import addbinvars, unionfind
data = np.array([list(s) for s in """\
AABCCCDDDD
AABCCCEEEF
GGGGHHIIIF
GGGGHHIIIF
JKLLHHIIIF
JKLLMMMNNN
JOLLMMMNNN
PQQRRRSSTT
PQQUUUSSVV
PQQUUUSSVV""".splitlines()])
nums = {'A':2, 'I':5, 'K':0, 'L':1, 'N':2, 'O':1, 'P':2, 'U':3}
nw, nh = len(data[0]), len(data)
Pythonで解く
数理モデルを作成し、解きましょう。
変数
- v：0:white, 1:black (1)
制約
- 3つの部屋で白をまっすぐ連続してはいけません (2)
- 数字は部屋内の黒の数となること (3)
- 黒は連続しないこと (4)
- 黒で分断しないこと (5)
python
m = LpProblem()
v = np.array(addbinvars(nh, nw)) # 0:white, 1:black (1)
for d, x in chain(zip(data,v), zip(data.T,v.T)):
b = np.arange(len(d)-1)[d[1:] != d[:-1]]
for i, j in zip(b, b[1:]+2):
m += lpSum(x[i:j]) >= 1 # (2)
for k, d in groupby(sorted(zip(data.flat, v.flat)), lambda x:x[0]):
if k in nums:
m += lpSum(c[1] for c in d) == nums[k] # (3)
for e in chain((v[1:,:] + v[:-1,:]).flat, (v[:,1:] + v[:,:-1]).flat):
m += e <= 1 # (4)
def dirs(i, j):
return [(i+y-x)*nw + j+y+x-1 for y in range(2) for x in range(2)
if 0 <= i+y-x < nh and 0 <= j+y+x-1 < nw]
while True:
m.solve()
r = np.vectorize(value)(v).astype(int)
u = unionfind(nh * nw)
if unionfind.isconnected(1-r, u):
break
dc = defaultdict(list)
for i, j in product(range(nh), range(nw)):
if r[i,j]:
for l in set(u.find(k) for k in dirs(j, i)):
dc[l].append(v[i][j])
for s in dc.values():
m += lpSum(s) <= len(s) - 1 # (5)
結果の表示
python
data[r==1] = '#'
print('\n'.join(' '.join(i) for i in data))
>>>
# A B # C C D # D #
A # B C C # E E E F
G G # G H H # I # F
G G G # H H I # I F
# K L L # H # I # F
J K # L M # M N N N
J # L L # M M # N #
# Q Q R R R # S T T
P Q Q # U # S S # V
# Q Q U # U S # V V
解けていることが確認できます。
以上