組合せ最適化でN Queen問題を解く

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\}$	1行に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つ以下

Pythonで解いてみる

定式化して解いてみましょう。

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

以上