Solving the N Queens problem with combinatorial optimization

What is the N Queen problem?

Place N queens on the N x N board. At this time, No piece should be in a position where it can be taken by another piece.

This problem can also be solved with Combinatorial Optimization (http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721).

Formulation

Objective function None
Variables $ x_j \ in \ {0, 1 \} ~ ~ \ forall j \ in Each cell $ Whether to put it in that cell td>
Constraints $ \ sum_ {j \ in Each cell ~~~~~} {\ {x_j | Vertical is i columns \}} = 1 ~ ~ \ forall i \ in \ {0, \ cdots, N-1 \} $ One per column
$ \ sum_ {j \ in each cell ~~~~~} {\ {x_j | side is i line \}} = 1 ~ ~ \ forall i \ in \ {0, \ cdots, N -1 \} $ One per line
$ \ sum_ {j \ in Each cell ~~~~~} {\ {x_j | Vertical + horizontal is i \}} \ le 1 ~ ~ \ forall i \ in \ {0, \ cdots , 2 N-2 \} $ One or less diagonal
$ \ sum_ {j \ in Each cell ~~~~~} {\ {x_j | Vertical-horizontal i-N + 1 \}} \ le 1 ~ ~ \ forall i \ in \ { 0, \ cdots, 2 N-2 \} $ One or less diagonal

Try to solve with Python

Let's formulate and solve it.

python3


%matplotlib inline
import pandas as pd, matplotlib.pyplot as plt
from itertools import product
from ortoolpy import addvar
from pulp import *
def NQueen(N):
    r = range(N)
    m = LpProblem()
    a = pd.DataFrame([(i, j, addvar(cat=LpBinary))
        for i, j in product(r, r)], columns=['Vertical', 'side', 'x'])
    for i in r:
        m += lpSum(a[a.Vertical== i].x) == 1
        m += lpSum(a[a.side== i].x) == 1
    for i in range(2*N-1):
        m += lpSum(a[a.Vertical+ a.side== i].x) <= 1
        m += lpSum(a[a.Vertical- a.side== i-N+1].x) <= 1
    %time m.solve()
    return a.x.apply(value).reshape(N, -1)
for N in [8, 16, 32, 64, 128]:
    plt.imshow(NQueen(N), cmap='gray', interpolation='none')
    plt.show()
>>>
CPU times: user 4 ms, sys: 4 ms, total: 8 ms
Wall time: 27.5 ms

CPU times: user 16 ms, sys: 4 ms, total: 20 ms
Wall time: 84.4 ms

CPU times: user 48 ms, sys: 4 ms, total: 52 ms
Wall time: 272 ms

CPU times: user 236 ms, sys: 0 ns, total: 236 ms
Wall time: 1.88 s

CPU times: user 956 ms, sys: 20 ms, total: 976 ms
Wall time: 11.3 s

image

that's all

Recommended Posts

Solving the N Queens problem with combinatorial optimization
Solving 4-color problems with combinatorial optimization
Pave the road with combinatorial optimization
Solving game theory with combinatorial optimization
Solving nurse scheduling problems with combinatorial optimization
Solving the nurse scheduling problem (shift optimization) with a genetic algorithm
Try to solve the N Queens problem with SA of PyQUBO
Solving Knapsack Problems with Google's OR-Tools-Practicing the Basics of Combinatorial Optimization Problems
Solving the Python knapsack problem with the greedy algorithm
Solving the iris problem with scikit-learn ver1.0 (logistic regression)
Grouping games with combinatorial optimization
Combinatorial optimization with quantum annealing
Maximize restaurant sales with combinatorial optimization
Go see whales with combinatorial optimization
The power of combinatorial optimization solvers
C language 8 queens problem solving 3 patterns
Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem
Let's solve the portfolio with continuous optimization
Let's stack books flat with combinatorial optimization
We will implement the optimization algorithm (Problem)
Solve the traveling salesman problem with OR-Tools
Solving the traveling salesman problem with the genetic algorithm (GA) and its library (vcopt)
Try to solve the fizzbuzz problem with Keras
Combinatorial optimization to find the hand of "Millijan"
Let's decide the date course by combinatorial optimization
Minimize the number of polishings by combinatorial optimization
Judging the finish of mahjong by combinatorial optimization
Solving the Lorenz 96 model with Julia and Python
I tried to solve the virtual machine placement optimization problem (simple version) with blueqat
Use combinatorial optimization
Combinatorial optimization-Typical problem-Facility placement problem with no capacity constraints
Solving the shortest path problem (VRP) Mixed integer programming
Try to solve the internship assignment problem with Python
The first algorithm to learn with Python: FizzBuzz problem
○○ Solving problems in the Department of Mathematics by optimization
python chrome driver ver. Solving the problem of difference
The 14th offline real-time writing reference problem with Python
I tried to solve the problem with Python Vol.1