조합 최적화로 몇 코로 풀기

이게 뭐야

문제

입력 파라미터

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)

파이썬으로 풀기

변수

제약

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)

결과 표시

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 .