조합 최적화로 크릭 풀기

Advent Calendar 9 일째 기사 조합 최적화로 초코나 풀기
Advent Calendar 11 일 기사 조합 최적화로 스타 배틀 풀기

이게 뭐야

크릭을 Python으로 조합 최적화 모델을 만들어 풀어 라.
푸는 재미는 모델링을 고안하는 것입니다.

자신도 시도하고 싶은 사람은 아래를 참조하십시오.

스도쿠를 통해 조합 최적화를 배우자.

문제

일부 송어를 검은 색으로 칠합니다.

숫자는 숫자가 인접한 매스에 있는 검은 매스의 수를 나타냅니다.

모든 흰 송어는 연결한다.

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



파이썬에서는 data (숫자라면 힌트)를 사용하기로 결정합니다.

파이썬

import pandas as pd, matplotlib.pyplot as plt
from pulp import LpProblem, lpSum, value
from ortoolpy import addbinvars, unionfind
data = """\
....1.
0.....
..3.4.
.2.12.
...1.1
......""".splitlines()

변수 테이블

아래와 같은 변수 테이블을 작성합니다. 각 행의 변수(Var)는 0 또는 1을 취합니다.
변수의 값이 1이면 해당 행 해당 열의 매스가 해당 수가 됩니다.


행
열
Var

0
0
0
v000001

1
0
1
v000002

...
...
...
...


파이썬

ni, nj = len(data)-1, len(data[0])-1
a = pd.DataFrame([(i,j) for i in range(ni)
    for j in range(nj)], columns=['行','列'])
a['Var'] = addbinvars(len(a))
a[:2]

수리 모델을 만들어 풀다

변수 테이블이 생겼으므로 크릭의 해가 되도록 제약 조건을 추가하여 수리 모델을 작성하고 풀어 봅시다.

숫자의 힌트는 주위의 검은 수.

흰색이 연결되어 있는 것.

제약 조건으로서 쓸 수도 있습니다만, 힘들기 때문에, 여기에서는 일단 무시해 풀 것입니다.

대답이 연결되어 있지 않을 때 그 대답을 금지하고 다시 풉니다.

연결되어 있는지 여부는 unionfind.isconnected 로 할 수 있습니다.

파이썬

m = LpProblem()
m += lpSum(a.Var)
for i in range(ni+1):
    for j in range(nj+1):
        if data[i][j].isdigit():
            q = f'{i-1}<=行<={i}&{j-1}<=列<={j}'
            m += lpSum(a.query(q).Var) == int(data[i][j])
while True:
    m.solve()
    r = a.Var.apply(value)
    if unionfind.isconnected((r!=1).values.reshape(ni,nj)):
        break
    m += lpSum(a[r==1].Var) <= (r==1).sum()-1

결과 표시

파이썬

plt.imshow((1-r).values.reshape(ni,nj), cmap='gray', interpolation='none')
plt.show()

풀리고 있는지 확인할 수 있습니다.

이상