Advent Calendar 18日目の記事 組合せ最適化で四角に切れを解く
Advent Calendar 20日目の記事 組合せ最適化でビルディングを解く
これなに
数コロを、Pythonで組合せ最適化モデルを作って解きます。
解く楽しみは、モデル化を工夫することになります。
自分でも試してみたい人は、下記を参考にしてください。
問題
- 全てのマスを１から４の数字か空白にします。
- 数字は、そのマスの隣接マスに数字が入るマスの数になります。
- 同じ数字を連続してはいけません。
- すべての数字を連結すること。
下記は、左が問題で、右が答えです。
入力パラメータ
dataにヒントが入っているとします。
python
import numpy as np
from itertools import chain, product
from pulp import LpProblem, lpSum, lpDot, value
from ortoolpy import addvars, addbinvars
data = """\
..1...1
.1.3.32
.......
.2.4.4.
.......
31.1.3.
1...1..""".splitlines()
nw, nh = len(data[0]), len(data)
Pythonで解く
数理モデルを作成し、解きましょう。
変数
- v：0:white, 1-4:number (1)
- r：数字 (2)
制約
- 数字があればその数字 (3)
- 数字は1つ (4)
- rをvで表現 (5)
- 数字は周りの数字の数に等しいこと (6)
- 同じ数字は連続しないこと (7)
- 全ての数字がつながること (8)
python
m = LpProblem()
v = np.array(addbinvars(nh, nw, 5)) # 0:white, 1-4:number (1)
u = np.zeros((nh+2, nw+2), dtype=object)
u[1:-1,1:-1] = v[:,:,1:].sum(2)
w = u[1:-1,2:]+u[1:-1,:-2]+u[2:,1:-1]+u[:-2,1:-1]
r = np.array(addvars(nh, nw)) # (2)
for i, j in product(range(nh), range(nw)):
if data[i][j].isdigit():
m += v[i,j,int(data[i][j])] == 1 # (3)
m += lpSum(v[i,j]) == 1 # (4)
m += lpDot(range(5), v[i,j]) == r[i,j] # (5)
m += w[i,j] >= r[i,j] # (6)
m += w[i,j] <= r[i,j] + 4*v[i,j,0] # (6)
for k in range(1, 5):
for e in chain((v[1:,:,k]+v[:-1,:,k]).flat, (v[:,1:,k]+v[:,:-1,k]).flat):
m += e <= 1 # (7)
while True:
m.solve()
s = np.vectorize(value)(r).astype(int)
break
if unionfind.isconnected(s==0):
break
m += lpSum(v[r==0]) >= 1 # (8)
結果の表示
python
t = s.astype(str)
t[s==0] = '.'
print('\n'.join(' '.join(s) for s in t))
>>>
1 . 1 2 . . 1
3 1 . 3 2 3 2
2 . . 2 . 2 .
3 2 3 4 2 4 1
2 . 2 3 . 2 .
3 1 . 1 . 3 1
1 . . . 1 2 .
解けていることが確認できます。
以上