Postscript: Reference link
-Solving puzzles by mathematical optimization --Qiita
Combinatorial optimization (bfbf4c185ed7004b5721) (so-called mixed integer optimization) allows you to write various rules simply. Here, we will briefly introduce some techniques using puzzles as an example. Some of these techniques are also part of Python. Python is a good match for modeling mathematical optimization.
--If you want to try it quickly: By using a service called Binder, you can try it only with a browser. For more information, see Introducing Binder, a free Jupyter service (821ebd608c412e57382d). --If you want to try it properly: After installing Anaconda, please execute the following.
pip install pulp ortoolpy unionfind more_itertools
PuLP is used as a modeler. (About PuLP) In the code example below, the following is omitted.
python
%matplotlib inline
import numpy as np, matplotlib.pyplot as plt
from itertools import groupby
from pulp import *
from unionfind import unionfind
from ortoolpy import addvar, addvars, addbinvar, addbinvars
m = LpProblem()
| Method | Description |
|---|---|
| group by | Group things with the same key |
| unionfind | [Disjoint Set Data Structure](https://ja.wikipedia.org/wiki/%E7%B4%A0%E9%9B%86%E5%90%88%E3%83%87%E3%83% Class for BC% E3% 82% BF% E6% A7% 8B% E9% 80% A0) |
| addvar | Create one variable |
| addvars | Create a list of variables |
| addbinvar | 0-1 Create one variable |
| addbinvars | 0-1 Create a list of variables |
| LpProblem | PuLP Mathematical Optimization Model |
I prepared it in SaitoTsutomu / OptForPuzzle.
Utility: Speed up calculation, various access Target puzzles: "Sudoku" etc. Example:
python
v = np.array(addbinvars(9, 9, 9)) # (1)
m += lpSum(v[i,:,k]) == 1 # (2)
m += lpSum(v[i:i+3,j:j+3,k]) == 1 # (3)
w = addvars(9, 9) # (4)
m += lpDot(range(9), v[i,j])+1 == r[i][j] # (4)
-In (1), a 0-1 variable of a 9x9x9 multidimensional array is created. Each dimension represents a row, a column, and a number. -In (2), it means that there is only one number $ k + 1 $ on the $ i $ line. -In (3), the upper left is a 3x3 area where $ (i, j) $, which means that there is only one number $ k + 1 $. --Also, using this $ v $, you can express the number of mass $ (i, j) $ as variable $ w_ {ij} $ as shown in (4).
Utility: Speed up calculation, various access Target puzzle: "Sudoku" etc. (Visualization is "Kuromasu" etc.) Example:
python
r = np.vectorize(value)(v).astype(int) # (1)
plt.imshow(1-r, cmap='gray', interpolation='none') # (2)
It is convenient to get the result $ r $ as shown in (1) above for the result of creating the variable with np.array and solving the optimization. This way, you can get results quickly and easily, and you can continue using numpy's versatile features. If you want to check the 2D black and white result as a figure, you can easily visualize it by using matplotlib as shown in (2).
If you manage variables with Series of DataFrame of pandas, you can do the same with apply.
Utility: Efficient modeling Target puzzle: "Paint area" etc. Example:
python
for vi, vj in zip(v, v[1:]):
m += vi == vj
If all the elements of the one-dimensional array $ v $ of variables must have the same value, you can write it as above. (There is also a way to replace the variable itself)
Utility: Efficient modeling Target puzzles: "Creek", "Shakashaka", "Several rollers", "Nori glue", "Paint area", "Bomber puzzle"
If you want to use the sum of the upper, lower, left, and right variables of the mass variable $ v [i, j] $, you can use $ w $ as shown below. Example:
python
u = np.zeros((nh+2, nw+2), dtype=object)
v = u[1:-1,1:-1] = np.array(addbinvars(nh, nw))
w = u[:-2,1:-1]+u[2:,1:-1]+u[1:-1,:-2]+u[1:-1,2:]
This is an example of using an array $ u $ that is one round more around v and using slices well.
Utility: Represents the case that holds depending on the conditions
Target puzzles: "Kanaore" etc.
If you have variables $ x, y $ and you want to make "$ y \ le a
python
m += y <= a + M(1-x)
Also, if you want to set "$ y = a
python
m += y <= a + M(1-x)
m += y >= a - M(1-x)
Utility: Easy modeling Target puzzle: "Kuromasu" etc.
There is a restriction that "all white squares are connected" like "Kuromasu". Trying to express such constraints with mathematical formulas can be quite difficult. Therefore, there is a way to ignore it once, and if it is not connected, prohibit the solution and solve it again.
Example: Checking connectivity
python
from unionfind import unionfind
r = np.array(
[[0,0,0],
[1,1,1],
[0,0,0]])
print(unionfind.isconnected(1-r))
r[1][1] = 0
print(unionfind.isconnected(1-r))
>>>
False
True
Suppose the resulting $ r $ represents 0: white and 1: black. You can check if white is connected with unionfind.isconnected (1-r). With this in mind, you can change the model until it is connected as shown below.
python
while True:
m.solve()
r = np.vectorize(value)(v).astype(int)
if unionfind.isconnected(1-r):
break
m += lpSum(v[r==1]) <= r.sum() - 1
The above code is simple, but it can be long to repeat for some puzzles. In that case, instead of "prohibiting all black squares in the result", it is possible to solve efficiently by "prohibiting the black squares surrounding the white" for each white area divided by the black squares. I can do it.
Utility: Simple input and programming Target puzzles: "Inshi no heya" "Country road" "Satogaeri" "Star battle" "Tile paint" "Chocona" "Nori glue" "Heyawake" "Paint area" Example:
python
data = """\
AABBB
AABCC
ADDDC
DDECC
EEEEC""".split()
v = np.array(addbinvars(nn, nn))
for _, d in groupby(sorted(zip(''.join(data), v.flat)), lambda x:x[0]):
m += lpSum(c[1] for c in d) == 1
The table of two-dimensional cells is divided into rooms as shown in the above data. At this time, the condition that "there is one black square in each room" can be simply written as above by using group by.
Utility: Easy modeling Target puzzles: "Kanaore", "Satogaeri", "Square cut", "Nurikabe", "Noguram", "Filmat", "Block puzzle", "Firefly beam"
When there are two 0-1 variables $ x and y $, if you want at most one of them to hold (= 1), you can do as follows.
Example:
python
m += x + y <= 1
If it is difficult to express the rules of the puzzle with mathematical formulas, it may be easy to model by enumerating the combinations that satisfy the rules and letting them choose from them. Such a formulation corresponds to the partitioning problem of the typical problem.
Let's take a look at the "Kanaore" candidate creation function. Example:
python
def makecand(lst, y, x, d, l, p, u):
yy, xx = y+[0, -1, 0, 1][d], x+[-1, 0, 1, 0][d] # (1)
if 0 <= yy < nh and 0 <= xx < nw and (yy,xx) not in u:
if p == l - 1:
lst.append(u + [(yy, xx)])
return
for k in range(4):
makecand(lst, yy, xx, k, l, p + 1, u + [(yy,xx)])
The argument d is the direction. Add 1 square in (1), and when p reaches the length, add it to lst and finish. If not, repeat the search in four directions. It would be difficult to model "Kanaole" in any other way. Modeling languages such as AMPL do not allow flexible writing. Using Python for modeling in this way can be very useful.
that's all
Recommended Posts