要約
Nクイーン問題とは、N×Nのチェス盤上にN個のクイーンを配置する問題であり、どのクイーンも互いに攻撃できないように配置する必要がある。チェスのクイーンは水平方向、垂直方向、および斜め方向に任意の距離だけ移動できるため、クイーンの隣接位置はこれらの3方向において衝突が生じないよう配置される必要がある。科学者たちは、この問題における分岐係数（branching factor）がほぼ線形に増加するという事実を認めている。幅優先探索（BFS）、深さ優先探索（DFS）、バックトラッキングなどの人工知能に基づく探索手法を用いて、多くの研究者がこの問題に取り組み、その解を求めるための多様な手法を提案している。BFSやDFSといった無情報探索（uninformed search）を含むブランチアプローチでは、再帰（recursion）が用いられる。また、バックトラッキングもこの問題の解法において再帰を活用している。これらすべての再帰的アルゴリズムはシステムスタックを用いるが、そのスタック容量には限界がある。そのため、Nの値が小さい場合でも、マシンの性能に依存してメモリが迅速に枯渇してしまう。本論文では、上記の問題に着目し、システムメモリを節約するための非再帰的DFS探索に基づくアプローチを提案する。本研究では、深さ優先探索（DFS）を無情報探索として用いている。実験的検証の結果、時間的および空間的効率の面で顕著な改善が得られた。