準備

nクイーン問題

$n$クイーン問題とは，$n \times n$のチェス盤の上に将棋の飛車と角行の動きを同時にできる駒（クイーン）をお互いに動きを妨げないように$n$個置く問題である．元は，そのような配置の個数を「数え上げる」問題であり， $8$クイーンの配置の総数をガウス(Johann Karl Friedruch Gauss: 1777-1855)が数え間違えたことは有名である．

しばしば，ランダムな配置を求める$n$クイーン問題が人工知能における充足可能性判定，ニューラルネットワーク，遺伝的アルゴリズムなど種々の分野で，テスト問題として用いられてきた．しかし，この問題はテスト問題として用いるほど困難ではなく，しかも実際問題への応用もほとんどない．したがって，この問題を組合せ最適化問題に対する解法の評価用に使うべきではない．

以下では，簡単な構築法とタブーサーチを用いた改善法で，$n$クイーン問題のランダムな配置が $O(n)$ 時間で求まることを示す．これを使うと$1000$万クイーン問題も解くことができる．

アルゴリズムと実装についての詳細は，拙著「組合せ最適化短編集」（朝倉書店）を参照されたい．

構築法とタブーサーチ

ユーティリティ関数を準備しておく．

 * is not TABU, or
 * is TABU but satisfies the aspiration criterion

次に，初期解を構築するための手法とタブーサーチによる改善法のコードを示す．

以下に実行例を示す．計算時間は平均的は $O(n)$ であり，大規模な問題例でも高速である（ただし，display関数による解の表示には時間がかかるので注意）．

%time
n = 30
sol=list(range(n))
up,dn=construct(sol)
ncolls = collisions(up) + collisions(dn)
print("collisions of randomized greedy :", ncolls)
if LOG:
    print("initial solution (random greedy):")
    print("array:" , sol)
    display(sol)
    print("queens on upward diagonals:", up)
    print("queens on downward diagonals:", dn)

print("starting fast tabu search")
fast_tabu_search(sol,up,dn)
ncolls = collisions(up) + collisions(dn)
print("collisions:", ncolls)

CPU times: user 3 µs, sys: 0 ns, total: 3 µs
Wall time: 4.77 µs
collisions of randomized greedy : 4
starting fast tabu search
iter= 0 swap 29 1 delta= 6
iter= 1 swap 28 0 delta= 4
iter= 2 swap 28 27 delta= 5
iter= 3 swap 28 13 delta= 5
iter= 4 swap 28 11 delta= 5
iter= 5 swap 28 26 delta= 5
collisions: 0

display(sol)

. . . . . . . . . . o . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . o . . . . . . . 
. . . . . o . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . o . . 
. . o . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . o . . . . . . . . . . . . 
. . . . . . . . . . . . . . o . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . o . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . o . . . . . 
. . . . . . o . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . o . . . . 
. . . . . . . . . . . . . . . o . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . o . . . 
o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . o . . . . . . 
. . . . o . . . . . . . . . . . . . . . . . . . . . . . . . 
. o . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . o . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . o . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . o . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . o . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . o . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 
. . . . . . . . . . . o . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . o . . . . . . . . . . 
. . . . . . . . o . . . . . . . . . . . . . . . . . . . . . 
. . . o . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . o . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . o . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . o .

nクイーン問題

準備