Edited at

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

More than 3 years have passed since last update.


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


image

以上