Nクイーン問題とは？バックトラッキングによる解法アルゴリズムをC++で解説

Nクイーン問題（N-Queens Problem）は、チェス盤の上にN個のクイーンを、どのクイーンも他のクイーンを攻撃できないように配置する方法を求める、古典的な組合せ最適化問題です。

チェスのクイーンは、縦・横・斜めのすべての方向に対して攻撃することができます。そのため、盤面上のどの2つのクイーンも同じ行・同じ列・同じ斜め線上に存在してはいけません。

この記事では、クイーンの配置位置を表すために0と1からなるバイナリ行列を使用します。1が置かれたマスにクイーンが配置され、どのクイーンも他のクイーンを攻撃しない状態を表します。

入力と出力

入力：
チェス盤のサイズ。通常は8（8×8が標準的なチェス盤のサイズです）。

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

以下は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

この出力において、値「1」はクイーンを配置すべき正しいマスを示し、「0」は空きマス（何も置かれていないマス）を表します。

アルゴリズム

この問題はバックトラッキングという手法を用いて解きます。各列に対して順番にクイーンを配置していき、衝突が発生したら直前の配置を取り消して別の行を試します。

isValid(board, row, col)

入力： チェス盤、および配置を検証する行と列。
出力： 指定された位置（row, col）へのクイーンの配置が有効であれば true、そうでなければ false。

Begin
    現在の列より左側の同じ行にクイーンが存在する場合
        return false
    左上方向の斜め線上にクイーンが存在する場合
        return false
    左下方向の斜め線上にクイーンが存在する場合
        return false
    上記以外の場合は有効な位置として true を返す
End

solveNQueen(board, col)

入力： チェス盤、およびクイーンを配置しようとしている列。
出力： クイーンが配置された位置行列。

Begin
    すべての列が埋まった場合
        return true
    盤面の各行について繰り返し処理を行う
        isValid(board, i, col) が true の場合
            盤面の (i, col) の位置にクイーンを配置する
            solveNQueen(board, col+1) が true を返した場合
                return true
            そうでなければ、(i, col) からクイーンを取り除く（バックトラック）
    return false
End

C++による実装例

#include<iostream>
using namespace std;
#define N 8

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();
}

実行結果

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

このプログラムは、左端の列から順にクイーンを配置し、各行について isValid 関数で攻撃関係がないかを検証しながら再帰的に探索を進めます。途中で行き詰まった場合は、直前に配置したクイーンを取り除いて次の候補を試すバックトラッキングによって、最終的に有効な解を1つ見つけ出します。