N Queen 문제란?

N × N의 판상에 N 개의 퀸을 배치한다. 이때,
어떤 조각은 다른 조각에 찍히는 위치에서 안된다.

이 문제도 조합 최적화에서 해결할 수 있습니다.

공식화

목적 함수
없음

변수
$x_j\in\{0, 1\} ~ ~\forall j\in 각 매스$
그 송어에 넣을지 여부

제약
$\sum_{j\in 각 매스~~~~~}{\{x_j|세로가 i열\}} = 1 ~ ~\forall i\in\{0,\cdots, N-1\}$
1열에 1개

$\sum_{j\in 각 매스~~~~~}{\{x_j|옆이 i행\}} = 1 ~ ~\forall i\in\{0,\cdots, N-1\}$
한 줄에 한

$\sum_{j\in 각 매스~~~~~}{\{x_j|세로+가로가 i\}}\le 1 ~ ~\forall i\in\{0,\cdots, 2 N-2\}$
대각선은 1개 이하

$\sum_{j\in 각 매스~~~~~}{\{x_j|세로-가로가 i-N+1\}}\le 1 ~ ~\forall i\in\{0,\cdots, 2 N-2\}$
대각선은 1개 이하

파이썬으로 풀어보세요

공식화하고 풀어 봅시다.

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=['縦', '横', 'x'])
    for i in r:
        m += lpSum(a[a.縦 == i].x) == 1
        m += lpSum(a[a.横 == i].x) == 1
    for i in range(2*N-1):
        m += lpSum(a[a.縦 + a.横 == i].x) <= 1
        m += lpSum(a[a.縦 - a.横 == 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

이상