3次元Nクイーン問題の解の存在の検証０７－１－０３７－０１０６前波大貴情報論理工学研究室目次        研究背景３次元Nクイーン問題の定義問題提起研究内容実行結果結論今後の課題研究背景  Nクイーン問題：サイズN×Nのチェス盤にN個のクイーンを互いの移動範囲を妨げないように配置する問題である。（N≧４）  N=26まで解が判明している。 Nクイーン問題 N=8のクイーンの移動範囲８方向   × × × × y × × × × Q × × × × × × Q Q × × × x (0,0) × × × ×  x (0,0) N=8の問題の解クイーン８個  Q × × Q × Q Q × Q × × (7,7) y Q (7,7) Nクイーン問題の解  Nクイーン問題の解：N個（N≧４）３次元Nクイーン問題の解  クイーンの最大配置可能数m(m≦N2) 理論上N≧１１の場合、m=N2 解が不明  実際に解の検証を行う   3次元Nクイーン問題     Nクイーン問題を３次元に拡張した問題立体のチェス盤上に、２６方向に直進できるクイーンを用いるお互いの移動範囲を侵略しないように配置解は存在する最大個数のクイーンを配置した配置パターンとその配置個数 3次元クイーンの移動範囲  N=５のチェス盤の中心 (2,2,2)のクイーンの移動範囲座標 (0,0,0) ×  クイーンの移動範囲のベクトルのイメージ図 x × × × × × y × × z=0 × × × × × × × × × × × z=1 × × × × × × × × × × × × × × (0,0,0) × × × × × × Q × × × × × × × × z=2 × (4,0,0) (0,4,0) Q (4,0,4) (0,4,4) × z=3 × × z=4 × (4,4,4) (4,4,4) 使用するアルゴリズム  バックトラック法：一つの探索手順を辿 (0,0,0) り、解が求められない Q と判明した時点で一つ前の状態に戻って別の手順を試す方法  (0,0,0)からx方向、y 方向、z方向に探索  設置可能なマスにクイーンを配置  最大個数を記録  最後に置いた駒を除く  探索順による次のマスから探索開始 x Q Q Q Q Q y Q Q z=0 z=1 z=2 Q Q Q Q Q Q z=3 z=4 (4,4,4) 実行結果  N=５までしか探索が行えず、十分な解の検証が行えなかった。 N 4 5  m 7 13 原因：膨大な探索時間予期せぬ実行中の中断探索時間 2秒 3300秒問題提起   発生した問題：膨大な探索時間予期せぬ実行中の中断問題の対策：探索時間の短縮探索途中のデータの記録と再生研究内容  発生した問題の対策  探索途中のデータの記録と再生：プログラムに機能として組み込む  探索時間の短縮：枝切り：設置個数から判定した探索手順の省略クイーンの初期配置の限定探索手順の省略    現在のクイーンの最大配置可能個数t 13 探索中に配置されているクイーンの個数q 11 探索予定の空きマスの数e 1 t-q≦e   現在の探索手順に過去のクイーン配置最大数を超えない現在の探索を省略、次の探索へ (0,0,0) Q x Q Q Q Q Q y Q Q z=0 z=1 z=2 Q Q Q Q Q z=3 z=4 (4,4,4) クイーンの初期配置の限定    クイーンの初期配置を少なくする初期配置からの長い探索手順が大幅に短縮される探索時間の短縮クイーンの初期配置の限定   チェス盤の中心から対称となる位置を省略 N=5のチェス盤の中心の座標(2,2,2)からの対称となる位置 x (0,0,0) 0 1 2 1 0 1 3 4 3 1 2 4 5 4 2 1 2 1 y 0 4 5 4 2 3 4 3 1 4 5 4 2 z=0 3 4 3 1 1 2 1 0 3 4 3 1 6 7 6 3 7 8 7 4 z=1 6 7 6 3 3 4 3 1 7 8 7 4 8 7 9 8 8 7 5 4 z=2 1 3 4 3 1 0 1 2 1 0 3 4 3 1 1 2 1 0 6 7 6 3 7 6 8 7 7 6 4 3 z=3 3 4 3 1 3 4 3 1 4 3 5 4 4 3 2 1 z=4 1 2 1 0 4 5 4 2 (4,4,4) クイーンの初期配置の限定  (0,0,0)からの探索手順で十分に探索できる初期配置を決める 125 (0,0,0) Q Q Q 10 x Q Q Q Q Q Q z=0 z=1 Q y z=3 z=2 z=4 (4,4,4) 対策後の実行結果  結果： N=６の探索完了 N=５の探索時間の短縮前回のNのサイズからの指数的な探索時間の増加量 N 4 5 6 m 7 13 21 探索時間 1秒 224秒 300時間以上結論   N=５の探索時間の短縮が成功したが、十分な解の検証が行えなかった新たな問題：前回のサイズからの指数的に増える探索時間の莫大な増加量今後の課題    N≧7の探索新たな問題：指数的な探索時間の増加量の十分な改善が必要今後の課題：新たな探索方法での探索高速計算に適した実行環境参考文献       柴田望洋：明解Javaによるアルゴリズムとデータ構造, pp.168—179, (2007). 吉瀬謙二,「N-queens Homepage in Japanese 」: 電気通信大学, 2004, http://www.arch.cs.titech.ac.jp/~kise/nq/index.htm 岡田章三：m次元nクイーン問題, 岐阜高専紀要第37号, pp.13—16, (2002). 岡田章三：m次元nクイーン問題に関する計算例と予測,岐阜高専紀要第38号,pp11－14, (2003). 岡田章三：m次元nクイーン問題に関する研究,岐阜高専紀要第39号,pp7－9, (2004). 岡田章三：m次元nクイーン問題に関する報告,岐阜高専紀要第40号,pp1－3, (2005). 終わりに  御静聴頂きありがとうございます。  本研究を完成するにあたって、御指導下さった石水隆先生と支援を受けた情報論理工学研究室の皆様に対して深く感謝を申し上げます。