3 次元 N クイーン問題の 解の存在の検証

3 次元 N クイーン問題の 解の存在の検証

０７－１－０３７－０１０６ 前波 大貴　 情報論理工学研究室

目次

 研究背景

 ３次元 N クイーン問題の定義

 問題提起

 研究内容

 実行結果

 結論

 今後の課題

研究背景

 N クイーン問題：

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

（ N≧ ４）

 N=26 まで解が判明している。

N クイーン問題

 N=8 のクイーンの 移動範囲

 ８方向

 N=8 の問題の解

 クイーン８個

x

y (0,0)

(7,7) Q

×

×

×

×

× ×

×

× ×

×

×

×

×

×

×

× × × ×

×

×

×

×

×

×

×

×

x

y (0,0)

(7,7) Q

Q

Q

Q

Q Q

Q

Q

N クイーン問題の解

 N クイーン問題の解： N 個（ N≧ ４）

 クイーンの最大配置可能数 m(m≦N²)

 理論上 N≧ １１の場合、 m=N²

 解が不明

 実際に解の検証を行う

３次元 N クイーン問題の解

3 次元 N クイーン問題

 N クイーン問題を３次元に拡張した問題

 立体のチェス盤上に、２６方向に直進できるクイー ンを用いる

 お互いの移動範囲を侵略しないように配置

 解は存在する最大個数のクイーンを配置した配置パ ターンとその配置個数

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

 N= ５のチェス盤の中心 (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)

使用するアルゴリズム

 バックトラック法：

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

 (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

Q

Q

Q

Q

Q Q

Q Q

実行結果

 N= ５までしか探索が行えず、十分な解の検証が行え なかった。

 原因：

膨大な探索時間

予期せぬ実行中の中断

N m 探索時間

4 7 2 秒

5 13 3300 秒

問題提起

 発生した問題：

膨大な探索時間

予期せぬ実行中の中断

 問題の対策：

探索時間の短縮

探索途中のデータの記録と再生

研究内容

 発生した問題の対策

 探索途中のデータの記録と再生：

プログラムに機能として組み込む

 探索時間の短縮：

枝切り：設置個数から判定した探索手順の省略 クイーンの初期配置の限定

探索手順の省略

 現在のクイーン の最大配置可能 個数 t

 探索中に配置さ れているクイー ンの個数 q

 探索予定の空き マスの数 e

 現在の探索手順 に過去のクイー ン配置最大数を 超えない

 現在の探索を省 略、次の探索へ

t - q ≦ e

x

y

(0,0,0)

z=0 z=1 z=2

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

Q

Q Q

Q Q

Q

Q

Q

Q

Q

Q Q

Q 13

11 1

クイーンの初期配置の限定

 クイーンの初期配置を少なくする

 初期配置からの長い探索手順が大幅に短縮される

 探索時間の短縮

クイーンの初期配置の限定

 チェス盤の中心から 対称となる位置を省 略

 N=5 のチェス盤の中 心の座標 (2,2,2) か らの対称となる位置

x

y

(0,0,0)

z=0 z=1 z=2

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

1 2 1 0

1 3 4 3 1

2

4 5 2 4

1 3 4 3 1

0 1 2 1 0

1 3 4 3 1

3 6 7 6 3

4

7 8 4 7

3 6 7 6 3

1 3 4 3 1

2 4 5 4 2

4 7 8 7 4

5

8 9 5 8

4 7 8 7 4

2 4 5 4 2 1

3 4 3 1

3 6 7 6 3

4

7 8 4 7

3 6 7 6 3

1 3 4 3 1

0 1 2 1 0

1 3 4 3 1

2

4 5 2 4

1 3 4 3 1

0 1 2 1 0

クイーンの初期配置の限定

 (0,0,0) からの探索手順で十分に探索できる初期配 置を決める

x

y

(0,0,0)

z=0 z=1 z=2

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

Q Q Q Q

Q Q Q Q Q

12 5

1

0

対策後の実行結果

 結果：

N= ６の探索完了

N= ５の探索時間の短縮

前回の N のサイズからの指数的な探索時間の増加量

N m 探索時間

4 7 1 秒

5 13 224 秒

6 21 300 時間以

上

結論

 N= ５の探索時間の短縮が成功したが、十分な解の検 証が行えなかった

 新たな問題：

前回のサイズからの指数的に増える探索時間の莫大 な増加量

今後の課題

 N≧7 の探索

 新たな問題：

指数的な探索時間の増加量の十分な改善が必要

 今後の課題：

新たな探索方法での探索 高速計算に適した実行環境

参考文献

 柴田望洋：明解 Java によるアルゴリズムとデータ構造 , p p.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).

終わりに



御静聴頂き

ありがとうございます。

 本研究を完成するにあたって、御指導下さった 石水隆先生と支援を受けた情報論理工学研究室 の皆様に対して深く感謝を申し上げます。