| Q | |||
| Q | |||
| Q | |||
| Q |
N クイーン問題 (下記を参照) は他のおおくの制約充足問題 (これについても下記を参照) と同様に，とくのに時間がかかります． そのため，それを高速にとくためのさまざまなくふうがかんがえられてきました． 金田の研究のなかでも，この問題をしばしば例題としてとりあげてきました．
最初は論理 / 記号 ベクトル処理 においてでした． Prolog のような論理型言語をつかうと， バックトラック という技法をつかった全解探索 (しらみつぶしの探索) をかんたんにプログラムすることができます． このようなプログラムをいかにして スーパーコンピュータのための高速なプログラムに変換するかが，この研究の課題でした． しかし，いくら高速化しても定数倍されるだけであり，指数的な計算時間がかかることにかわりはありません．
つぎにこの問題をとりあげたのは CCM (化学的計算のモデル)においてでした． CCM においては計算に最初からランダムさが導入されていて，従来の計算法におけるようにつねに完全に解をもとめることはめざしていません． このような確率的な計算をするばあいには指数的な計算時間は必要ありません． CCM をつかえばパソコンでも，スーパーコンピュータをつかったバックトラック解法より高速に解をもとめることができます． N クイーン問題とならべかえ (ソート) のページには Java をつかった CCM による N クイーン問題のプログラムがあり，この計算をためすことができます． このページではパラメタをかえていろいろなときかたをためすことができますが，それについてはべつの機会に書くことにします (上記のページにはだいたいのことが書いてあります)． 確率的な解法としてはほかにニューラルネットや遺伝的アルゴリズムをつかった方法などもありますが，CCM による解法もそれらと似た性質をもっています．
金田の研究からははずれますが， N クイーン問題は N. ヴィルト の 「アルゴリズムとデータ構造」 という本でも プログラミングの例題としてとりあげられていますし，のちに Prolog などにつながっていった R. W. Floyd の "Nondeterministic Algorithms" という論文 (Journal of the ACM, Vol. 14, No. 4 (1967), pp. 636-644) でもとりあげられています． 後者については金田が 「情報処理」 の 2003 年 2 月号 (Vol. 44, No. 2, p. 198) に 解説を書いています． この解説のなかにも書きましたが，量子計算の例題としてもつかわれています．
チェス盤に，たがいにとりあわないように 8 個のクイーンをおくおきかたをもとめるのがエイト・クイーン問題です． これを N × N の盤面に拡張したのが N クイーン問題です． N クイーン問題のようにある条件をみたす解をもとめる問題を 制約充足問題といいます． たとえば地図を 4 色でぬりわけるのも制約充足問題です． おおくの制約充足問題はしらみつぶしにしないと解をもとめることができない NP (Non-Polynomial) とよばれる，むずかしい問題のクラスに属しています． N クイーン問題もそういう問題のひとつです． Non-polynomial とよばれるのは，N に関する多項式であらわされる時間ではとけない (指数的な時間がかかる) からです．
[関連するページ: The N Queens Page]
