조합 최적화로 페인트 영역 풀기

Advent Calendar 12 일 기사 조합 최적화로 추리 퍼즐 풀기
Advent Calendar 14 일 기사 조합 최적화로 벽 로직 풀기

이게 뭐야

페인트 영역을 파이썬에서 조합 최적화 모델을 만들어 풀어 라.
푸는 재미는 모델링을 고안하는 것입니다.

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

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

문제

반면에 있는 굵은 선으로 구분된 부분(타일) 중 일부를 검은색으로 칠합니다.

반면의 숫자는, 그 숫자가 들어 있는 매스에 세로 옆에 인접하는 매스 중, 검은 매스가 되는 매스의 수를 나타냅니다.

숫자의 매스가 블랙 매스가 될 수도 있습니다.

어느 타일도, 모든 매스를 칠하거나 모든 매스를 젖지 않고 두는 어느 쪽으로 해, 타일의 일부의 매스만을 칠하지 말아 주세요.

모든 검은 송어는 연결됩니다.

흑백 매스 모두, 2×2 이상은 안된다.

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


data 에 타일의 그룹이, nums 에 힌트의 「행, 열, 개수」가 들어 있다고 합니다.

파이썬

import pandas as pd, matplotlib.pyplot as plt
from pulp import LpProblem, lpSum, value
from ortoolpy import addbinvars, unionfind
data = """\
AABBC
DEFBC
DGFHH
DGIJH
KKLJH""".splitlines()
nums = [[0,1,3], [3,2,2], [4,1,1]]

변수 테이블

아래와 같은 변수 테이블을 작성합니다. 각 행의 변수는 0 또는 1을 취합니다.
변수의 값이 1이면 해당 행 해당 열의 질량이 검정색입니다.
"자"는 data의 값입니다.


행
열
글자
Var

0
0
0
A
v000001

1
0
1
A
v000002

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


파이썬

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

수리 모델을 만들어 풀다

변수 테이블을 만들었으므로 페인트 영역의 해가되도록 제약 조건을 추가하고 수리 모델을 만들고 해결합시다.

2×2의 백색 및 2×2의 검정이 없을 것.

query 에서 2x2를 꺼내 검정색 수를 1,2,3으로 설정합니다.

타일내는 같은 것.

타일 내의 인접한 변수를 동일하게 합니다.

숫자는 주위의 검은 수와 같을 것.

상하좌우는, 차분의 절대치의 합이 1의 것입니다.

모든 검정이 연결되는 것.

연결되어 있지 않으면, 그 해의 전백의 매스에 적어도 1개 검정을 두고 풀어 다시 합니다.

파이썬

m = LpProblem()
for i in range(ni-1):
    for j in range(nj-1):
        e = lpSum(a.query(f'{i}<=行<={i+1}&{j}<=列<={j+1}').Var)
        m += e >= 1 # 2×2の白がない
        m += e <= 3 # 2×2の黒がない
for _,v in a.groupby('字'):
    for vi, vj in zip(v.Var, v.Var[1:]):
        m += vi == vj # タイル内は同じ
for i, j, k in nums: # 数字は周りの黒の数と等しい
    m += lpSum(a.query(f'abs(行-{i})+abs(列-{j})==1').Var) == k
while True:
    m.solve()
    r = a.Var.apply(value)
    if unionfind.isconnected(r.values.reshape(ni,nj)):
        break # 全ての黒がつながる
    m += lpSum(a[r==0].Var) >= 1

결과 표시

파이썬

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

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

이상