요인의 방을 풀다

요인의 방은 스도쿠와 비슷한 퍼즐입니다. 이 퍼즐도 조합 최적화을 사용하여 풀 수 있습니다.
참고
- 요인 방 wikipedia
- 요인 방 니콜리
- 스도쿠를 조합하여 최적으로 풀기

문제 예

니코리 님으로부터 승낙 받고, 예제를 빌렸습니다. 왼쪽이 문제이고 오른쪽이 답변입니다.
문제는 두꺼운 선으로 둘러싸인 방으로 나뉘며 왼쪽 상단에 힌트 숫자가 있습니다.
힌트는, 그 방내의 숫자의 곱셈이 되어 있습니다.
5×5 사이즈라면 사용할 수 있는 숫자는 1~5입니다. 스도쿠와 같이 세로 1행이나 가로 1열로, 같은 숫자는 사용할 수 없습니다.

공식화

조합 최적화의 모델에서 중요한 것은, 가능한 한 1차식으로 나타내는 것입니다.
단순히 변수의 곱셈을 모델링하면 비선형 최적화가되어 해결하기가 어렵습니다.
이번에는 로그를 사용하여 1 차식으로 만듭니다. 즉, 다음과 같이 파악할 수 있습니다.

$2\times 3 = 6$ → $\log(2) +\log(3) =\log(6)$

이렇게 하면 1차식으로 표현할 수 있습니다. 단, 이대로 있으면 무리수를 사용하므로 계산 오차가 발생합니다. 그래서 제약식을 등호가 아니라 미세한 범위에 들어가도록 지정합니다.

공식화는 다음과 같습니다.

$\mbox{variables}$
$x_{ijk}\in\{0, 1\} ~\forall i, j, k$
매스 i,j가 숫자 k+1인가 (1)

$y_{ij}\in\{1\cdots n\} ~\forall i, j$
송어 i, j의 숫자 (2)

$\mbox{subject to}$
$\sum_k{x_{ijk}} = 1 ~\forall i, j$
숫자는 1개 (3)

$\sum_k{x_{ikj}} = 1 ~\forall i, j$
세로에 같은 숫자는 없다 (4)

$\sum_k{x_{kij}} = 1 ~\forall i, j$
옆에 같은 숫자가 없다 (5)

$y_{ij}를 x_{ijk}로 나타내는 $(6)

송어의 곱은 힌트와 같습니다 (7)

파이썬으로 풀기

pulp 와 pandas를 사용합니다.

문제는 문자열에 있다고 가정합니다.

파이썬

ch = """
ABBCD
AEEFD
GGHFD
IJHKK
ILHMM
""".strip().split('\n')
rooms = [6, 15, 1, 12, 20, 8, 10, 6, 4, 4, 15, 1, 10]

준비합니다.

파이썬

import pandas as pd
from collections import defaultdict
from pulp import *
from math import log
def addvar(lowBound=0, count=[0], *args, **kwargs):
    count[0] += 1
    return LpVariable('v%d'%count[0], lowBound=lowBound, *args, **kwargs)
nn, nb = len(ch), len(rooms) # 数字の個数、部屋の数
rn, rb = range(nn), range(nb)
lognn = [log(k + 1) for k in rn] # 1..nnのlog
logrm = [log(h) for h in rooms] # ヒントのlog

변수 표를 만들어 보자.

파이썬

a = pd.DataFrame([(i, j, [addvar(cat=LpBinary) for k in rn], addvar())
                  for i in rn for j in rn],
                 columns=['縦', '横', 'Vars', 'Var']) # (1), (2)
print(a[:3])

세로 $i$ 가로 $j$ 의 Vars 는 [$x_{ijk}\forall k$] 에, Var 는 $y_{ij}$ 에 대응합니다.

세로
수평
Vars
Var




0
0
0
[v1, v2, v3, v4, v5]
v6


1
0
1
[v7, v8, v9, v10, v11]
v12


2
0
2
[v13, v14, v15, v16, v17]
v18



공식화하고 해결합니다.

파이썬

m = LpProblem() # 数理モデル
dic = defaultdict(list) # 部屋ごとの変数(x)のリスト
for _, r in a.iterrows():
    m += lpSum(r.Vars) == 1 # (3)
    m += lpDot(rn, r.Vars) + 1 == r.Var # (6)
    dic[ch[r.縦][r.横]].append(r.Vars)
for i in rn:
    for k in rn:
        m += lpSum(v[k] for v in a.query('縦==%d'%i).Vars) == 1 # (4)
        m += lpSum(v[k] for v in a.query('横==%d'%i).Vars) == 1 # (5)
for h in rb:
    c = lpSum(lpDot(lognn, v) for v in dic[chr(h + 65)]) # 数字の積のlog
    m += c >= logrm[h] - 0.001 # (7)
    m += c <= logrm[h] + 0.001 # (7)
m.solve() # 求解

결과를 표시합니다.

파이썬

a['Val'] = a.Var.apply(value)
print(a.Val.reshape(5, -1))
>>>
[[ 2.  3.  5.  1.  4.]
 [ 3.  5.  4.  2.  1.]
 [ 5.  2.  1.  4.  3.]
 [ 1.  4.  2.  3.  5.]
 [ 4.  1.  3.  5.  2.]]

이상