조합 최적화로 파급 효과 해결

이게 뭐야

문제

같은 숫자를 같은 가로 행이나 같은 세로 줄에 넣는 경우 숫자와 숫자 사이에 숫자와 같은 수 이상의 칸이 있어야합니다.

아래는 왼쪽이 문제이고 오른쪽이 대답입니다.

입력 파라미터

data 에 힌트가 들어 있다고 합니다.

파이썬

import numpy as np
from pulp import LpProblem, lpSum, lpDot, value
from ortoolpy import addvars, addbinvars
data = """\
...3..
......
..2..4
3..4..
......
..2...""".split()
rms = [[eval(t) for t in s.split('/')] for s in """\
0,0
0,1/0,2/1,2
0,3/1,3/1,4/2,3
0,4
0,5/1,5/2,4/2,5/3,5
1,0/1,1
2,0/3,0/3,1/4,1
2,1/2,2/3,2/4,2
3,3/4,3/5,1/5,2/5,3
3,4
4,0/5,0
4,4/4,5/5,5
5,4""".splitlines()]
nw, nh = len(data[0]), len(data)
na = max(len(rm) for rm in rms)

파이썬으로 풀기

수리 모델을 만들고 풀어 봅시다.

변수

제약

m = LpProblem()
v = addbinvars(nh, nw, na) # (1)
r = addvars(nh, nw) # (2)
def dirs(i, j, k):
    yield from (v[i+l][j][k] for l in range(1, k+2) if i+l < nh)
    yield from (v[i][j+l][k] for l in range(1, k+2) if j+l < nw)
for i in range(nh):
    for j in range(nw):
        if data[i][j].isdigit():
            m += r[i][j] == int(data[i][j]) # (3)
        m += lpSum(v[i][j]) == 1 # (4)
        m += lpDot(range(na), v[i][j]) + 1 == r[i][j] # (5)
        for k in range(na):
            m += lpSum(dirs(i,j,k)) <= 2*(1-v[i][j][k]) # (6)
for rm in rms:
    for k in range(len(rm)):
        m += lpSum(v[i][j][k] for i,j in rm) == 1 # (7)
m.solve()

결과 표시

print(np.vectorize(value)(r).astype(int))
>>>
[[1 2 1 3 1 2]
 [2 1 3 2 4 1]
 [4 3 2 1 5 4]
 [3 2 1 4 1 3]
 [2 1 4 1 3 1]
 [1 5 2 3 1 2]]