3次元Nクイーン問題の 解の存在の検証 ０７－１－０３７－０１０６ 前波 大貴 情報論理工学研究室 宜しくお願いします。 前波　大貴 情報論理工学研究室 宜しくお願いします。 情報論理工学研究室の前波大貴です。 「3次元Nクイーン問題の解の存在の検証」の研究発表をします

目次 研究背景 ３次元Nクイーン問題の定義 問題提起 研究内容 実行結果 結論 今後の課題

研究背景 Nクイーン問題： サイズN×Nのチェス盤にN個のクイーンを互いの 移動範囲を妨げないように配置する問題である。 （N≧４）

Nクイーン問題 N=8のクイーンの 移動範囲 N=8の問題の解 クイーン８個 ８方向 x y (0,0) (7,7) Q × x y

Nクイーン問題の解 ３次元Nクイーン問題の解 Nクイーン問題の解：N個（N≧４） クイーンの最大配置可能数m(m≦N2) 理論上N≧１１の場合、m=N2 解が不明 実際に解の検証を行う ３次元Nクイーン問題の解 Nクイーン問題の解はN個です。 ここでNクイーン問題を3次元に拡張した、3次元Nクイーン問題の解について言及します。 3次元の解はクイーンの最大配置可能数mとすると、 クイーンの直進的に移動する性質と、チェス盤の１面の大きさがN×Nの性質から Nの２乗の個数がクイーンの配置の限界だとわかります。 文献では理論上Nが11以上の場合、m=N2成立しますが、しかし実際の各Nの解は求められていません。 なので、各Nの解を求め、解の法則性を検証します。

3次元Nクイーン問題 Nクイーン問題を３次元に拡張した問題 立体のチェス盤上に、２６方向に直進できるクイーンを用 いる お互いの移動範囲を侵略しないように配置 解は存在する最大個数のクイーンを配置した配置パ ターンとその配置個数 それでは3次元Nクイーン問題の定義をします。 N×N×Nの立体のチェス盤上に、3次元的な26方向に直進できるクイーンを用いります。 そのほかはNクイーン問題と同様に、お互いの移動範囲を侵さないように配置し、解は存在する最大個数のクイーンを配置した配置パターンとその配置個数です。

3次元クイーンの移動範囲 N=５のチェス盤の中心 (2,2,2)のクイーンの移動 範囲座標 クイーンの移動範囲のベ クトルのイメージ図 (0,0,0) x (0,0,0) × × × × × × × × × × × × (4,0,0) (0,4,0) × × × × × × × × Q × × × × × × × × y × 先ず、3次元のクイーンの移動方向についてN=5のチェス盤で説明します。 クイーン配置した時に平面方向に８方向に移動、上方向に９方向、下方向に９方向移動でき、合計26方向に移動が可能です。 × × × × × z=0 z=1 z=2 Q × × × × × × × × × × × × (4,0,4) × × × (0,4,4) × × × (4,4,4) (4,4,4) z=3 z=4

使用するアルゴリズム (0,0,0) x Q Q Q Q Q Q y Q Q z=0 z=1 z=2 Q Q Q Q Q Q (4,4,4) バックトラック法： 一つの探索手順を辿 り、解が求められない と判明した時点で一つ 前の状態に戻って別 の手順を試す方法 (0,0,0)からx方向、y 方向、z方向に探索 設置可能なマスにク イーンを配置 最大個数を記録 最後に置いた駒を除く 探索順による次のマ スから探索開始 (0,0,0) x Q Q Q Q Q Q y Q Q z=0 z=1 z=2 Q 使用するアルゴリズムはバックトラック法を用いります。 （Qを配置しながら探索手順の説明） 配置可能マスがないとき、配置個数が最大か確認します。 これ以上配置できないので～ また新しい手順で検索を開始します。 Q Q Q Q Q (4,4,4) z=3 z=4

実行結果 N m 探索時間 4 7 2秒 5 13 3300秒 N=５までしか探索が行えず、十分な解の検証が行えな かった。 原因： 膨大な探索時間 予期せぬ実行中の中断 N m 探索時間 4 7 2秒 5 13 3300秒 このアルゴリズムで実行しましたが、N=5までしか探索が行えず、十分な解の検証が行えませんでした。 原因として考えられるのは、膨大な探索時間とその探索途中での予期せぬ実行中の中断でした。

問題提起 発生した問題： 膨大な探索時間 予期せぬ実行中の中断 問題の対策： 探索時間の短縮 探索途中のデータの記録と再生 発生した問題： 膨大な探索時間 予期せぬ実行中の中断 問題の対策： 探索時間の短縮 探索途中のデータの記録と再生 本研究の課題として、3次元Nクイーン問題の定義と実行をしましたが、 十分な解の検証が行えなえず、 発見した問題として、膨大な探索時間と予期せぬ実行中の中断 この問題の対策として探索時間の短縮と、 探索途中のデータの記録と再生を図りたいと思います。

研究内容 発生した問題の対策 探索途中のデータの記録と再生： プログラムに機能として組み込む 探索途中のデータの記録と再生： プログラムに機能として組み込む 探索時間の短縮： 枝切り： 設置個数から判定した探索手順の省略 クイーンの初期配置の限定 発見した問題の対策として、探索時間の短縮は、 設置個数から判定した探索手順の省略とクイーンの初期配置の限定を行い。 探索途中のデータの記録と再生はプログラムに機能を組み込みます。

t - q ≦ e 探索手順の省略 現在のクイーンの 最大配置可能個 数t 探索中に配置され ているクイーンの 個数q 現在の探索手順 に過去のクイーン 配置最大数を超え ない 現在の探索を省 略、次の探索へ (0,0,0) x Q Q Q 13 Q Q 11 Q y Q Q 1 z=0 z=1 z=2 t - q ≦ e Q 先ず、探索手順の省略について説明します。 最初の探索手順でクイーンを置きった後、現在のクイーンの最大配置可能個数tとして記録します。 ～ 基本バックトラック法のように駒を消して新しい手順を試す時。探索予定の空きマスの数値eを確認します。 Q Q Q Q (4,4,4) z=3 z=4

クイーンの初期配置の限定 クイーンの初期配置を少なくする 初期配置からの長い探索手順が大幅に短縮される 探索時間の短縮 クイーンの初期配置の限定を説明します。 クイーンの初期配置を少なくすると、初期配置からの長い探索手順が大幅に短縮されます。 そして探索時間の短縮に繋がります。

クイーンの初期配置の限定 チェス盤の中心から 対称となる位置を省 略 N=5のチェス盤の中 心の座標(2,2,2)から の対称となる位置 (0,0,0) x 1 2 1 1 3 4 3 1 2 4 5 4 2 1 3 4 3 1 3 6 7 6 3 4 7 8 7 4 2 4 5 4 2 4 7 8 7 4 5 8 9 8 5 1 3 4 3 1 3 6 7 6 3 4 7 8 7 4 y 1 2 1 1 3 4 3 1 2 4 5 4 2 z=0 z=1 z=2 1 3 4 3 1 1 2 1 それでは、クイーンの初期配置の限定位置について説明します。 ～ 3 6 7 6 3 1 3 4 3 1 4 7 8 7 4 2 4 5 4 2 3 6 7 6 3 1 3 4 3 1 1 3 4 3 1 1 2 1 (4,4,4) z=3 z=4

125 10 クイーンの初期配置の限定 (0,0,0)からの探索手順で十分に探索できる初期配置を 決める x (0,0,0) Q Q Q Q y z=0 z=1 z=2 (4,4,4) z=3 z=4

対策後の実行結果 N m 探索時間 4 7 1秒 5 13 224秒 6 21 300時間以上 結果： N=６の探索完了 N=５の探索時間の短縮 前回のNのサイズからの指数的な探索時間の増加量 N m 探索時間 4 7 1秒 5 13 224秒 6 21 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).

御静聴頂き ありがとうございます。 終わりに 御静聴頂き ありがとうございます。 本研究を完成するにあたって、御指導下さった石水 隆先生と支援を受けた情報論理工学研究室の皆様 に対して深く感謝を申し上げます。