조합 최적화로 스타 배틀 풀기

Advent Calendar 10 일 기사 조합 최적화로 크릭 풀기
Advent Calendar 12 일 기사 조합 최적화로 추리 퍼즐 풀기

이게 뭐야

스타 배틀을 Python으로 조합 최적화 모델을 만들어 풀어줍니다.
푸는 재미는 모델링을 고안하는 것입니다.

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

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

문제

각 행, 각 열, 각 영역에 ★를 정확히 하나 놓는다.

★ 주위(8곳)에 ★는 둘 수 없다.

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



파이썬에서는 data (영역 그룹)을 사용하기로 결정합니다.

파이썬

import pandas as pd, matplotlib.pyplot as plt
from pulp import LpProblem, lpSum, value
from ortoolpy import addbinvars
data = """\
AABBB
AABCC
ADDDC
DDECC
EEEEC""".splitlines()

변수 테이블

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


행
열
글자
Var

0
0
0
A
v000001

1
0
1
A
v000002

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


파이썬

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

수리 모델을 만들어 풀다

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

각 행, 각 열, 각 영역에 ★를 정확히 하나 놓는다.

['行','列','字'] 마다, groupby 하고, 합을 1 로 합니다.

★ 주위(8곳)에 ★는 둘 수 없다.

2x2 매스 안에 ★를 1개 이하로 하면 OK입니다.

파이썬

m = LpProblem()
for cl in ['行','列','字']:
    for _,v in a.groupby(cl):
        m += lpSum(v.Var) == 1
for i in range(nn-1):
    for j in range(nn-1):
        q = f'{i}<=行<={i+1}&{j}<=列<={j+1}'
        m += lpSum(a.query(q).Var) <= 1
m.solve()

결과 표시

파이썬

a['Val'] = a.Var.apply(value)
plt.imshow((a.Val<0.5).values.reshape(nn,nn), cmap='gray', interpolation='none')
plt.show()

별답입니다만, 제약은, 만족하고 있는 것 같습니다.

이상