Combinatorial optimization techniques seen in puzzles

Postscript: Reference link

-Solving puzzles by mathematical optimization --Qiita

Introduction

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.

Environment

--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

Preparation

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

Target puzzle

I prepared it in SaitoTsutomu / OptForPuzzle.

Technique

Create variables with np.array

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).

Get the result with np.vectorize

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.

All the same

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)

Number around

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.

IF constraint

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 " if " x == 1 $", use a sufficiently large number $ M $ as shown below. You can write. Example:

python


m += y <= a + M(1-x)

Also, if you want to set "$ y = a " if " x == 1 $", you can write as follows. Example:

python


m += y <= a + M(1-x)
m += y >= a - M(1-x)

Concatenation constraints

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.

Processing by area (room or country)

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.

Select from candidates

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

Combinatorial optimization techniques seen in puzzles
Solving "cubes in cubes" by combinatorial optimization
Python in optimization
Use combinatorial optimization
Grouping by combinatorial optimization
Performance optimization in Django 3.xx
Combinatorial optimization to investigate stars
Grouping games with combinatorial optimization
Techniques for sorting in Python
Combinatorial optimization with quantum annealing
Solve optimization problems in Python