C++で解くN-クイーン問題：バックトラッキングによるアルゴリズムと実装例

N-クイーン問題とは、チェス盤上にN個のクイーンを配置し、どのクイーンも他のクイーンを攻撃できないようにする配置を見つける古典的な組合せ問題です。

チェスのクイーンは、水平・垂直・斜めのあらゆる方向に攻撃できます。そのため、互いに干渉しない配置を見つけるには、単純な全探索ではなく効率的なアルゴリズムが必要になります。

本記事では、0と1からなる二値行列でクイーンの位置を表現し、8クイーン問題を例に、バックトラッキングを用いた解法をC++で実装する方法を解説します。

入力

チェス盤のサイズを指定します。ここでは一般的なチェス盤と同じ8×8を想定しています。

出力

N個のクイーンを配置できる行と列を表す行列が出力されます。解が存在しない場合はfalseを返します。

1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0

この出力では、値「1」がクイーンの正しい配置位置を、「0」がチェス盤の空きマスを表しています。

アルゴリズム

この問題は「バックトラッキング」という手法で効率的に解けます。ある列にクイーンを置いたものの、後続の列でどこにも配置できなくなった場合には、直前の選択を取り消して別の行を試します。これを繰り返すことで、無駄な探索を大幅に削減できます。

isValid(board, row, col)

指定した位置(row, col)にクイーンを配置できるかどうかを判定する関数です。現在の列より左側にある同じ行・左上方向の斜め・左下方向の斜めに、既にクイーンが存在していないかを確認します。

開始
    現在の列より左側の同じ行にクイーンが存在するならば
        falseを返す
    左上方向の斜めにクイーンが存在するならば
        falseを返す
    左下方向の斜めにクイーンが存在するならば
        falseを返す
    trueを返す // 上記に当てはまらなければ有効な配置位置
終了

solveNQueen(board, col)

バックトラッキングにより再帰的に解を探索するメインの関数です。各列に対して、クイーンを置ける行を順番に試していきます。

開始
    すべての列が埋まったならば
        trueを返す
    盤面の各行 i について繰り返し
        isValid(board, i, col) が真であれば
            位置(i, col)にクイーンを置く
            solveNQueen(board, col+1) が true を返せば
                trueを返す
            そうでなければ、位置(i, col)からクイーンを取り除く
    falseを返す
終了

C++による実装例

以下は、上記のアルゴリズムをC++で実装したサンプルコードです。処理の流れが分かるよう、コメントを付けています。

#include<iostream>
using namespace std;
#define N 4
void printBoard(int board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << board[i][j] << " ";
        cout << endl;
    }
}
bool isValid(int board[N][N], int row, int col) {
    for (int i = 0; i < col; i++) //左側にクイーンが存在するかチェック
        if (board[row][i])
            return false;
    for (int i=row, j=col; i>=0 && j>=0; i--, j--)
        if (board[i][j]) //左上方向の斜めにクイーンが存在するかチェック
            return false;
    for (int i=row, j=col; j>=0 && i<N; i++, j--)
        if (board[i][j]) //左下方向の斜めにクイーンが存在するかチェック
            return false;
    return true;
}
bool solveNQueen(int board[N][N], int col) {
    if (col >= N) //N個のクイーンをすべて配置できた場合
        return true;
    for (int i = 0; i < N; i++) { //各行について、クイーンを配置できるかチェック
        if (isValid(board, i, col) ) {
            board[i][col] = 1; //有効であれば位置(i, col)にクイーンを置く
            if ( solveNQueen(board, col + 1)) //残りの列を再帰的に探索
                return true;
            board[i][col] = 0; //配置できる場所がなければクイーンを取り除く
        }
    }
    return false; //有効な配置が見つからない場合
}
bool checkSolution() {
    int board[N][N];
    for(int i = 0; i<N; i++)
    for(int j = 0; j<N; j++)
    board[i][j] = 0; //すべての要素を0で初期化
    if ( solveNQueen(board, 0) == false ) { //0列目から探索を開始
        cout << "Solution does not exist";
        return false;
    }
    printBoard(board);
    return true;
}
int main() {
    checkSolution();
}

※ サンプルコードでは #define N 4 として4×4盤面を解いていますが、これを #define N 8 に変更すれば、次節に示す8×8盤面の出力と同じ結果が得られます。

出力結果

1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0

まとめ

N-クイーン問題は、バックトラッキングの考え方を学ぶのに最適な題材です。制約を満たすかどうかを都度判定しながら再帰的に探索を進め、行き詰まったら一手戻る――このシンプルな仕組みは、数独やパズル求解など、さまざまな組合せ最適化問題に応用できます。ぜひ盤面サイズNを変更して、動作や計算時間の変化を試してみてください。