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
以上