조합 최적화로 오노 풀기

Advent Calendar 24 일 기사 조합 최적화로 헛소리 풀기

이게 뭐야

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

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

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

문제

매스에 빨강 ● 또는 파랑 ●을 반드시 넣을 수 있습니다

*는 빨간색 ● 지정을 나타냅니다

숫자는 자신도 파란색으로 취급하고 자신감을 제외한 상하 좌우로 이어지는 파란색 ●의 수를 나타냅니다.

혼자 파랑 ●은 금지합니다

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

입력 파라미터

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

파이썬

import numpy as np
from itertools import product
from pulp import LpProblem, lpSum, value
from ortoolpy import addvars, addbinvars
data = """\
4...
3...
...*
*23.""".splitlines()
n = len(data)

파이썬으로 풀기

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

공식화

\begin{array}{cl}
            変数 & x_{ij} \in \{0, 1\} ~ \forall i, j ~ ~ ~ マスi,jが青●か (1) \\
            変数 & y_{ijk} \ge 0 ~ \forall i, j, k ~ ~ ~ マスi,jの方向kの青●連続数 (2) \\
\mbox{subject to} & yをxで表す (3) \\
                 & 数字や*の指定 (4) \\
                 & 単独青●の禁止 (5) \\
\end{array}

파이썬

def cons(m,x,y,i,j,k,dx,dy,bdi,bdj):
    if i == bdi or j == bdj:
        m += y[i,j,k] == 0 # (3)
    else:
        m += y[i,j,k] <= y[i+dx,j+dy,k]+1 # (3)
        m += y[i,j,k] <= x[i+dx,j+dy]*(n-1) # (3)
        m += y[i,j,k] >= y[i+dx,j+dy,k]+1 - n*(1-x[i+dx,j+dy]) # (3)
m = LpProblem()
x = np.array(addbinvars(n, n)) # 青●か (1)
y = np.array(addvars(n, n, 4)) # 縦、横、上右下左の連続数 (2)
m += lpSum(x) # (3)
for i, j in product(range(n),range(n)):
    cons(m,x,y,i,j,0,-1, 0,  0,-1)
    cons(m,x,y,i,j,1, 0, 1, -1,n-1)
    cons(m,x,y,i,j,2, 1, 0,n-1,-1)
    cons(m,x,y,i,j,3, 0,-1, -1,0)
    if data[i][j] == '*':
        m += x[i,j] == 0 # (4)
    elif data[i][j].isdigit():
        m += x[i,j] == 1 # (4)
        m += lpSum(y[i,j]) == int(data[i][j]) # (4)
    else:
        m += lpSum(y[i,j]) >= x[i,j]
m.solve()

결과 표시

파이썬

print(np.vectorize(value)(x).astype(int))
>>>
[[1 1 1 0]
 [1 1 0 0]
 [1 0 1 0]
 [0 1 1 1]]

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

요약

퍼즐이라는 테마로 조합 최적화는 어땠습니까?
「재미있어! 해보자!」라고 느끼실 수 있으면 다행입니다.

참고: 수리 최적화에 의한 퍼즐 해법

참고: 퍼즐에서 보는 조합 최적화 기술

이상