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