[PYTHON] Optimal solution by combining "factor rooms"
Solve the factor room
** Inshi no heya ** is a puzzle similar to Sudoku. This puzzle can also be solved using Combinatorial Optimization (http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721). reference -Factor Room wikipedia -Factor Room Nikoli -Sudoku is combined and solved optimally
Problem example
With the consent of Nikoli, I borrowed an example. The left is the question and the right is the answer. The problem is divided into rooms surrounded by thick lines, with hint numbers in the upper left. The hint is the multiplication of the numbers in the room. For a 5x5 size, the numbers you can use are 1-5. As with Sudoku, the same numbers cannot be used in one vertical row or one horizontal column.
Formulation
The important thing in the combinatorial optimization model is to express it as a linear expression as much as possible. Simply modeling variable multiplication results in non-linear optimizations that are difficult to solve. This time, we will use logarithms to make a linear expression. In other words, you can think of it as follows.
In this way, it can be expressed as a linear expression. However, if it is left as it is, an irrational number will be used and a calculation error will occur. Therefore, specify the constraint expression so that it falls within a small range instead of an equal sign.
The formulation is as follows.
| $ \ mbox {variables} $ | $ x_ {ijk} \ in \ {0, 1 \} ~ \ forall i, j, k $ | Is the cell i, j the number k + 1? (1) |
| $ y_ {ij} \ in \ {1 \ cdots n \} ~ \ forall i, j $ | Numbers i, j (2) | |
| $ \ mbox {subject to} $ | $ \ sum_k {x_ {ijk}} = 1 ~ \ forall i, j $ | One number (3) |
| $ \ sum_k {x_ {ikj}} = 1 ~ \ forall i, j $ | No vertical same number (4) | |
| $ \ sum_k {x_ {kij}} = 1 ~ \ forall i, j $ | There is no same number next to it (5) | |
| $ y_ {ij} is represented by x_ {ijk} $ (6) | ||
| The product of squares is equal to the hint (7) | ||
Solve with Python
[pulp](http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721#%E3%82%BD%E3%83%95%E3%83%88%E3%81%AE%E3%82 Use% A4% E3% 83% B3% E3% 82% B9% E3% 83% 88% E3% 83% BC% E3% 83% AB) and pandas.
The problem is that it's in a string.
python
ch = """
ABBCD
AEEFD
GGHFD
IJHKK
ILHMM
""".strip().split('\n')
rooms = [6, 15, 1, 12, 20, 8, 10, 6, 4, 4, 15, 1, 10]
Get ready.
python
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) #Number of numbers, number of 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] #Hint log
Let's make a table of variables.
python
a = pd.DataFrame([(i, j, [addvar(cat=LpBinary) for k in rn], addvar())
for i in rn for j in rn],
columns=['Vertical', 'side', 'Vars', 'Var']) # (1), (2)
print(a[:3])
--Vars of vertical $ i $ horizontal $ j $ correspond to [$ x_ {ijk} \ forall k $], and Var corresponds to $ y_ {ij} $.
| Vertical | Horizontal | 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 |
Formulate and solve.
python
m = LpProblem() #Mathematical model
dic = defaultdict(list) #Variables for each room(x)List of
for _, r in a.iterrows():
m += lpSum(r.Vars) == 1 # (3)
m += lpDot(rn, r.Vars) + 1 == r.Var # (6)
dic[ch[r.Vertical][r.side]].append(r.Vars)
for i in rn:
for k in rn:
m += lpSum(v[k] for v in a.query('Vertical==%d'%i).Vars) == 1 # (4)
m += lpSum(v[k] for v in a.query('side==%d'%i).Vars) == 1 # (5)
for h in rb:
c = lpSum(lpDot(lognn, v) for v in dic[chr(h + 65)]) #Log of product of numbers
m += c >= logrm[h] - 0.001 # (7)
m += c <= logrm[h] + 0.001 # (7)
m.solve() #Solution
Display the result.
python
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.]]
that's all