探索による問題解決の事例

1.1 N-Queen問題

チェスに縦横ナナメに長く移動できるQueenという駒がある。Queenの動きは図1を参照。

図1  Queenの可能な動き

N-Queen問題 (N-Queens Problem) とは、縦横 N 個 × N 個 のマスからなるボードに、N 個のチェスのクイーン駒を相互に利きがぶつからないように配置する問題で、チェス盤 (縦横 8 × 8 マス) に8個のクイーンを配置する 8-Queen問題 の一般化されたものである。

図2に N = 7 のときの解答の一つを示す。

図2  N-Queen問題で N = 7 のときの一解答

本来はすべての配置を数え上げる問題で、探索量が指数関数的に爆発するため現在でも N = 30 近くが限界となっている。

今回の問題では、最初は、設定を「1個でも配置を見つければよい」探索問題とする。
後で、すべての配置を数え上げる問題も対応する。

※ 実は、解を1個求めるだけなら、探索をせず、特定の規則でQueenを置いていくだけで解が生成できることが知られている。後の節を参照のこと。

今回の問題を解くために、まず固定サイズの際の素朴な探索アルゴリズムを考え、次に、サイズを変更可能とするため、再帰 (recursion) を用いた深さ優先探索を適用する。

1.2 基本的手法と素朴なアルゴリズム

まず、問題解決のための基本的手法を考える。
N-Queen問題の解には

• クイーンは必ず各列に一個
• クイーンは必ず各行に一個
• ナナメ右上あるいは右下方向には、クイーンがないか、もしくは一個ある

という特徴がある。 これから、

左(０列目)の列から順に右に、
        列のうちのクイーンを置けるマスのどこか
        (上のマスから順に試す)に配置してゆく。
列にクイーンが置けなくなったら
        一つ前の列に戻って、別のマスを試す。
        もう試すマスがないときは、さらにもう一つ前の列に戻る。
全部のクイーンが配置できたら終了。

という手順が考えられる。

探索の様子がわかるプログラム NQueenSearch.jar をTeams授業チーム「共有済み」の下の NQueen フォルダに置いてあるので、実行して色々試してみるとよい。 ダウンロードし、PowerShell またはコマンドプロンプトを起動し、ファイルを置いてあるフォルダに cd で移動した後、

というコマンドでプログラムが起動できる。

いきなり問題を一般化して解くのではなく、まずはクイーンの数の小さい問題で考えてみるとよい。
4-Queen問題について、実際に順番に配置をして調べていく動作を素朴に記述してみる。

０列目のすべてのマスについて {
        クイーンを置く
        一列目のすべてのマスについて {
                置けるマスならば {
                        クイーンを置く
                        二列目のすべてのマスについて {
                                置けるマスならば {
                                        クイーンを置く
                                        三列目のすべてのマスについて {
                                                置けるマスならば {
                                                        クイーンを置く
                                                        解を見つけた。表示し終了
                                                }
                                        }
                                        置いたクイーンを戻す
                                }
                        }
                        置いたクイーンを戻す
                }
        }
        置いたクイーンを戻す
}

1.3 データ表現とサポート処理群

プログラムのデータ表現を考える。

ボードの大きさ(=クイーンの数 N)は値を変更できるよう変数 (boardSize とする) で表す。
なお、プログラムの都合上、縦および横のインデックスの最大値を表す N - 1 = boardSize - 1 の値を変数 boardSize_1 に覚えておく。

Java では

ボードのデータを boardSize × boardSize の二次元配列 (boardData とする) で表し、

static final int DEFAULT_BOARD_SIZE = 8; // ボードの大きさ(=クイーンの数)のデフォルト値
int boardSize = DEFAULT_BOARD_SIZE;
int boardSize_1 = boardSize - 1;
boolean[][] boardData = new boolean[boardSize][boardSize];

のように記述できる。上記のように boardData 配列を new で確保した場合、配列のすべての要素が false で初期化されている。

ボード上の行と列を 0 から始め boardSize 未満の範囲 (boardSize - 1 まで) とし、行は上が 0 で下に行くに従い増加、列は左が 0 で右に行くに従い増加するとする。 ボード上 i行j列 のマスのデータが boardData[i][j] で表されるとする。

boardData[i][j] が

ことを表す。

C言語では

ボードのデータを 最大サイズ × 最大サイズ の二次元配列 (boardData とする) で表し、

#define MAX_BOARD_SIZE 40  // ボードの大きさ(=クイーンの数)の最大値
const int DEFAULT_BOARD_SIZE = 8;  // ボードの大きさ(=クイーンの数)のデフォルト値
int boardSize = DEFAULT_BOARD_SIZE;
int boardSize_1 = boardSize - 1;
unsigned char boardData[MAX_BOARD_SIZE][MAX_BOARD_SIZE];

のように記述できる。

C言語で、関数の外部でグローバルに boardData 配列を定義した場合、すべての要素が 0 で初期化されており、false とみなせる。

※ 論理型・論理定数の扱い

C99 以降の規格に準拠しているCコンパイラの場合は、先頭付近で

#include <stdbool.h>

として標準ヘッダをインクルードすれば、論理型 bool と false, true を使用できる。

さらに、新しい C23 規格 (2024年10月発行) では bool, false, true はキーワードになり、stdbool.h はインクルード不要で、そのまま bool, false, true を使用できる。ただし、2026年9月現在、C23 規格に十分に対応しているC処理系はまだそれほど多くない。

逆に、stdbool.h のない相当古いCコンパイラを使っている場合は、例えば

typedef int bool;
#define true 1
#define false 0

のように定義すれば bool, false, true を使用できるが、そういったコンパイラでは他にも新しい記述法に対応していない点があるので、ソースの多くの箇所を修正する必要がある。

次に、マスにクイーンが置けるかどうかをチェックするため、

• ある行にクイーンが置かれているかどうかを示す一次元配列 (rowPlaced とする)
• 左上斜め方向にクイーンが置かれているかどうかを示す一次元配列 (diagNWPlaced とする)
• 左下斜め方向にクイーンが置かれているかどうかを示す一次元配列 (diagSWPlaced とする)

を用意する。

Java では

boolean[] rowPlaced = new boolean[boardSize];
boolean[] diagNWPlaced = new boolean[2*boardSize - 1];
boolean[] diagSWPlaced = new boolean[2*boardSize - 1];

のように記述できる。
rowPlaced, diagNWPlaced, diagSWPlaced 各配列を上記のように new で確保すると、配列のすべての要素が false で初期化されている。

C言語では

unsigned rowPlaced[MAX_BOARD_SIZE];
unsigned diagNWPlaced[2*MAX_BOARD_SIZE - 1];
unsigned diagSWPlaced[2*MAX_BOARD_SIZE - 1];

のように記述できる。関数の外部で配列を定義した場合、配列のすべての要素が 0 で初期化されており、false とみなせる。

リスト2のアルゴリズムを記述する上で必要になる細かい処理を以下に示す。

ボードデータの初期化

ボードのデータをすべて空とする
(boardData, rowPlaced, diagNWPlaced, diagSWPlaced 各配列のすべての要素を false にする。)
※ Java では、new で boolean 配列を確保すると各要素は false で初期化されるので、プログラムが一回しか問題を解かないのであれば不要。
※ C 言語では、関数の外あるいはstaticな変数として宣言した場合、プログラムが一回しか問題を解かないのであれば不要。

クイーンを置く、置いたクイーンを戻す、置けるかどうかのチェック

クイーンを i行j列 に置く {
	boardData[i][j] = true
	rowPlaced[i] = true
	diagNWPlaced[i - j + boardSize_1] = true
	diagSWPlaced[i + j] = true
}

クイーンをある列に置くと、その右側の列の以下のマスにはもうクイーンは置けない。

そのクイーンを置いた行のマス	⇒	rowPlaced[i] = true で表す
そのクイーンを置いたマスのナナメ右下方向にあるマス	⇒	diagNWPlaced[i - j + boardSize_1] = true で表す
そのクイーンを置いたマスのナナメ右上方向にあるマス	⇒	diagSWPlaced[i + j] = true で表す

i行j列 に置いたクイーンを戻す {
	boardData[i][j] = false
	rowPlaced[i] = false
	diagNWPlaced[i - j + boardSize_1] = false
	diagSWPlaced[i + j] = false
}

ある列にクイーンを取り去ると、その右側の列の以下のマスにはクイーンが置けるようになる。

そのクイーンを置いた行のマス	⇒	rowPlaced[i] = false で表す
そのクイーンを置いたマスのナナメ右下方向にあるマス	⇒	diagNWPlaced[i - j + boardSize_1] = false で表す
そのクイーンを置いたマスのナナメ右上方向にあるマス	⇒	diagSWPlaced[i + j] = false で表す

i行j列 にクイーンが置けるかどうかのチェック {
(ただし、j列以降にはクイーンはまだ置かれていない状態)
	「rowPlaced[i] が false」
		かつ「diagNWPlaced[i - j + boardSize_1] が false」
		かつ「diagSWPlaced[i + j] が false」
	であればOKなので true を返す。
	それ以外はNGなので false を返す。
}

該当マスの行のマス、該当マスのナナメ右下・右上方向のマス、すべてにクイーンがまだ置かれていなければ、そのマスにはクイーンが置ける。そうでなければ置けない。

1.4 再帰を使ったアルゴリズム

リスト2の方法は、無駄にループが深くなり、クイーンの数の変化に対応できない、という問題点がある。そこでリスト2のアルゴリズムを参考に、再帰呼び出しを使ったスマートなコードに書き換えてみる。

プログラムは、メイン部分から、探索のための search メソッド (関数) を呼び出し、search の中で searchSub メソッド (関数) を呼び出す形とする。実際に再帰しているのは searchSub メソッド (関数) である。

整数型 search() {
	r = searchSub( boardSize )
	r を返り値として呼び出し元に戻る
}

整数型 searchSub( n ) {  // n は未配置クイーンの残り枚数
	n1 = n - 1   // n1 は次の段階での未配置クイーンの残り枚数
	(boardSize - n)列目のすべての行iのマスについて {
	    置けるマスならば {
	        クイーンを i行(boardSize - n)列 に置く
	        n1 が 0 なら {
	                配置成功なので、1 を返り値として呼び出し元に戻る
	        }
	        r = searchSub( n1 )
	        r が 0 でなければ {
	                配置が見つかったので、r を返り値として呼び出し元に戻る
	        }
	        i行(boardSize - n)列 に置いたクイーンを戻す
	    }
	}
	配置失敗。0 を返り値として呼び出し元に戻る
}

プログラムの中で

        r = search()

のように search メソッド (関数) を呼び出し返り値を整数型の変数 r に代入すれば答を見つけることができる。
返り値 r が 0 でなければ配置が見つかったので、解を出力すればよい。返り値 r が 0 のときは解が存在しないことが保証される。

1.5 ボード二次元配列を使わない方法

今まで説明したN-Queen問題解答プログラムでは、ボードデータの表現として

サイズ boardSize × boardSize の二次元配列 (boardData とする) で表し、

という形式を使っている。

しかし、N-Queen問題の解では各列 (または各行) に必ず一個のQueenが配置されるという条件が成立するため、ボードを表す配列を使わず、一次元配列 rowPlaced を各行の何列目にクイーンが置かれているかを表すように変えるとボードデータを表現できる。ボード配列を使ったときと比べ、少なくとも使用メモリ量を削減でき、また実行速度アップも期待できる。
※ 実際の実行速度には、より複雑な複数の要因が関係するため、今回の変更で必ずしも速くなるとは限らない。

この表現では、rowPlaced 配列の意味を変えて

という形式にすればよい。

このとき、上記の変更に伴い、以下の変更をプログラムに加える必要がある。

変数定義部分で、boardDataの削除とrowPlacedの型を int 配列に変更

ソースにある boardData 定義の行は削除する。

rowPlaced は int 型の配列に変更する。

ボードデータの初期化

boardData配列の初期化用コードはすべて削除する。

rowPlaced配列のインデックス 0 〜 boardSize - 1 までのすべての要素を -1 にする。(初期化必須)
diagNWPlaced, diagSWPlaced 各配列については前と同様。

※ 雛形ソースを基にしている場合は、setBoardSize 関数 (メソッド) に変更を加えること。

クイーンを i行j列 に置く

boardDataに関するコードは削除する。

	rowPlaced[i] = j

diagNWPlaced, diagSWPlaced 各配列の更新については前と同様。

i行j列 に置いたクイーンを戻す

boardDataに関するコードは削除する。

	rowPlaced[i] = -1

diagNWPlaced, diagSWPlaced 各配列の更新については前と同様。

i行j列 にクイーンが置けるかどうかのチェック

「rowPlaced[i] が false」をチェックしている部分を以下のように rowPlaced[i] がマイナスであるかどうかをチェックするように変更する。

	rowPlaced[i] < 0

diagNWPlaced, diagSWPlaced 各配列のチェックについては前と同様。

解を表示する関数 (メソッド) printSolution (雛形ソースを基にしている場合) 内の修正

	if ( boardData[i][j] ) {

の行を

	if ( rowPlaced[i] == j ) {

に変更。

以上の変更を加えて、探索プログラムを書き換え動作させる。

1.6 解の数を求めるプログラム

前述したように、本来のN-Queen問題は解の数を求める問題である。 小さい N と解の数の対応を表1に示す。

※ 下表の「解の総数」は回転や鏡映で同一となる配置も複数のままカウントして求めた総数である。対称性を考慮した場合の本質的に異なる解の数を下の段「基本解の数」に示す。

この講義では再帰を使った数え上げ・探索の基本的演習問題としてN-Queen問題を扱っており、プログラムに特別な工夫などは入れておらず、数え上げ速度については大きく改善の余地があるが、あくまでもこのページの説明の範囲で、できるだけ速く解の数を数え上げるプログラムを作ってもらえばよい。

今回のプログラムも、メイン部分から search 関数(メソッド)を呼び出し、search の中で再帰用の searchSub を呼び出す形とする。search では、対称性を考慮して、ボードの最初の列だけは、上半分の行を調べて得られた値を2倍することで効率化している。ただし、ボードのサイズが奇数の場合は最後にちょうど真ん中になる行を調べる。

今回の searchSub 関数(メソッド) は、リスト3のコードを変更して、見つかった「解の総数」を返すためのコードとする。下記の擬似コードになる。なお、search および searchSub 関数(メソッド)の型は「解の総数」を返すのに適した整数型とする。

リスト中、countRot180 は180度回転で変わらない解の個数、countRot90 は90度回転で変わらない解の個数、をそれぞれ表す変数であり、外部で定義されており、共に初期値 0 となっている。

「180度回転で変わらない解の個数」と「90度回転で変わらない解の個数」は外部変数を直接更新していくが、「解の総数」だけは再帰呼び出し階層で下層から上層に向かって伝播・更新されていく形となっているので注意すること。

解が見つかると、count に1加えた後、まず180度回転で変わらない解かどうかを調べる。
変わらない解の場合は countRot180 に1加え、さらに90度回転で変わらない解かどうかを調べ、変わらなければ countRot90 に1加える。

整数型 searchSub( n ) {
    // n は未配置クイーンの残り枚数を表す
    n1 = n - 1
    n1 が 0 なら {
            整数型  count = 0
            boardSize_1 列目のすべての行iのマスについて {
                    置けるマスならば {
                            クイーンを i行 boardSize_1 列 に置く   // rowPlaced[i] = boardSize_1 だけでも可
                            // 配置成功 (解を一つ見つけた)
                            count に 1 加える
                            180度回転で変わらなければ {
                                    countRot180 に 1 加える
                                    90度回転で変わらなければ
                                            countRot90 に 1 加える
                            }
                            i行 boardSize_1 列 に置いたクイーンを戻す   // rowPlaced[i] = -1 だけでも可
                    }
            }
            count を返り値として呼び出し元に戻る
    }

    // 以下は n1 > 0 のとき

    整数型  count = 0
    (boardSize - n)列目のすべての行iのマスについて {
            置けるマスならば {
                    クイーンを i行(boardSize - n)列 に置く
                    count += searchSub( n1 )
                    i行(boardSize - n)列 に置いたクイーンを戻す
            }
    }
    count を返り値として呼び出し元に戻る
}

解の数を求めるプログラムについて、C言語の雛型ファイル nqueencount_proto.c または Javaの雛形ファイル NQueenCount_proto.java をTeamsの授業チーム「共有済み」の下の NQueen フォルダからダウンロードし、それを追加・修正して動作させる。なお、Javaのファイルはファイル名を NQueenCount.java に変更する必要がある。
ただし、実行速度が要求されるので、できるだけJavaをやめてC言語のプログラムを作ることを勧める。

まず、探索版プログラムのボード二次元配列を使わない方法で作ったプログラムを参考にして、数え上げのプログラム TODO 部分で追加・修正・削除を行う。
ソースから boardData がすべて消えるはずである。

また、リスト4に示した擬似コードを使用言語のソースに直して searchSub 関数(メソッド)の中身として入力する。

180度回転で変わらない解かどうかは equalRot180 関数(メソッド)を呼び出して返ってきた値でチェックする。
90度回転で変わらない解かどうかは equalRot90 関数(メソッド)を呼び出して返ってきた値でチェックする。ただし、equalRot90 は180度回転で変わらないと判明している解に対して90度回転でも変わらないかどうかを調べるものであることに注意する必要がある。

なお、正方形ボードの対称操作 (回転(90度・180度・270度)、鏡映(上下・左右・対角線2つ)、恒等操作(何もしない)、全部で8個) から成る対称変換群 D₄ を考える。
N-Queen問題の性質から、鏡映によって変わらない解は存在せず、90度回転で変わらない解は270度回転でも変わらないので、群論のバーンサイドの補題により、基本解 (fundamental solutions : 対称性を考慮した場合の本質的に異なる解) の数は以下の式で求まる。

基本解の数 = (解の総数 + 2 × 90度回転で変わらない解の数 + 180度回転で変わらない解の数) ÷ 8

数学的知識を要し、この講義の内容を超えるので詳細には立ち入らないが、興味のある人はバーンサイドの補題、対称性などのキーワードで調べてみるとよい。

1.7 特定規則による解の生成

N-Queenの解を1個求めるだけであれば、解を生成する特定規則が知られている。
行および列のインデックスを 0 オリジンで記述すると下記の手順となる。