3 次元 n クイーン問題の解に関する研究

(1)

3 次元 n クイーン問題の解に関する研究

08-1-037-0149 　論理工学研究室伊藤精一　

(2)

n クイーン問題



背景



研究内容



結果・考察



今後の課題

(3)

n クイーン問題



n×n の盤上に n 個のクイーンを縦・

横・斜めの 8 方向の直線上に 1 個のクイーンしか存在しないように配置する問題



n=8 のクイーンの移動範囲

(0,0) x

y (7,7)

× Q

×

(4)

n クイーン問題



n クイーン問題は n

≧4 以上の場合、 n

×n マス上に n 個のクイーンを配置できる



n=4 の例

Q

× ×

× Q ×

× × Q

×

× ×

×

Q ×

(3,3) x

y

(0,0)

(5)

n クイーン問題の今までの研究



n クイーンの解の総数

　既存の結果だと求められた n の最大数は 26 　発見された解の数はおよそ 2 京

　結果を求めるのに要した時間はおよそ 9 ヶ月



探索時間の短縮

n クイーン問題の研究は、これらの研究が非常に多い

(6)

n クイーン問題の応用



n クイーン最小個数問題



3 次元 n クイーン最小個数問題

これらの問題を取り上げる

(7)

ｎクイーン極大配置問題



n×n の盤上に m(≦n) 個のクイーンを配置した時、新たに m+1 個目のクイーンがどこにも置くことができないような配置を解とする



n=4 の例

Q

× ×

× Q ×

× × Q

×

× ×

×

Q ×

(3,3) x

y

(0,0)

(8)

n クイーン最小個数問題とは



極大配置解 m の値が最小となる問題

・ n=4 の解の例　

Q

Q Q

× × ×

×

× ×

×

× ×

(4,4) x

y (0,0)

(9)

3 次元 n クイーンとは



n クイーン問題の n×n マスを n×n×n の 3 次元に拡張した問題



配置したクイーンの影響する範囲が 2 次元の 8 方向から 3 次元の 26 方向に増加する



3 次元の 26 方向の直線上に 1 つのクイーンしか存在

しないように配置する

(10)

3 次元 n クイーンの移動範囲



n=5 のチェス盤の中心 (2,2,2) のクイーンの移動範囲座標



クイーンの移動範囲のベクトルのイメージ図

x

y

(0,0,0)

z=0 z=1 z=2

z=3 z=4 (4,4,4)

Q

×

× ×

×

× ×

×

× ×

×

× ×

×

× ×

×

× ×

×

× ×

×

× ×

×

Q (0,0,0)

(4,0,0) (0,4,0)

(0,4,4)

(4,0,4) (4,4,4)

(11)

使用するアルゴリズム

 バックトラック法：

一つの探索手順を辿り、解が求められないと判明した時点で一つ前の状態に戻って別の手順を試す方法

 (0,0,0) から x 方向、 y 方向、 z 方向に探索

 設置可能なマスにクイーンを配置

 設置可能なマスがなくなった時点でその個数を記録

 最後に置いたクイーンを撮り除く

 探索順による次のマスから探索開始

 新たに設置可能なマスがなくなり、その個数が前の記録より小さい場合、新しくその個数を記録

 再び探索を行う

x

y

(0,0,0)

z=0 z=1 z=2

z=3 z=4 (4,4,4)

Q

Q Q

Q

Q Q

(12)

2 次元 n クイーンの最小個数解ｍの実行結果



n の値が小さい場合、 n の値が増えても m の値は急に増

えることはなかった

(13)

3 次元 n クイーンの最小個数解 m の実行結果



3 次元 n クイーンは、探索時間を大幅に要し、得られた解が少なく、有意なデータを得られな

かった

(14)

実行結果・考察



3 次元 n クイーン問題の 解に関する研究