C++ で Eight Queens 問題アルゴリズムを使用する方法

C での 8 クイーン問題アルゴリズムの使用方法

8 クイーン問題は、8 x 8 のチェス盤上に 8 つのクイーンを配置する必要がある古典的なアルゴリズム問題です。クイーンは互いに攻撃できます。つまり、2 つのクイーンが同じ行、列、または対角線上に存在することはできません。 Eight Queens 問題を解決するには多くのアルゴリズムがありますが、一般的な方法の 1 つはバックトラッキング アルゴリズムを使用することです。この記事では、C 言語を使用してエイト クイーン問題のアルゴリズムを実装する方法と、具体的なコード例を紹介します。

まず、2 次元配列で表される 8x8 のチェス盤を定義する必要があります。配列の各要素はチェス盤のグリッドを表すことができます。1 はグリッド上にクイーンがあることを意味し、0 はクイーンが存在しないことを意味します。

次に、ボードの各行を調べてクイーンを配置する再帰関数を定義します。具体的な手順は次のとおりです。

1. チェス盤の最後の行まで移動した場合は、解決策が見つかったことを意味し、現在のチェス盤の状態を保存して戻ります。
2. 現在の行の各グリッドを移動し、クイーンを配置してみます。
3. 現在のグリッドがクイーンを配置するための条件を満たしていない場合 (つまり、すでに配置されているクイーンと競合している場合)、現在のグリッドはスキップされ、次のグリッドのトラバースが継続されます。
4. 現在のグリッドがクイーンを配置するための条件を満たしている場合、グリッド上にクイーンを配置し、グリッドを占有済みとしてマークします。
5. 関数を再帰的に呼び出し、次の行を移動します。
6. 再帰呼び出しの結果が true を返した場合、解決策が見つかったことを意味し、解決策は保存され、true が返されます。
7. 再帰呼び出しの結果が false を返した場合は、現在のグリッドの配置がソリューションの要件を満たしていないことを意味します。グリッド上のクイーンを削除して、前のステップに戻ります。

上記の考えに基づいて、次のコードを実装できます:

#include <iostream>
#include <vector>

using namespace std;

const int n = 8;  // 棋盘大小

// 棋盘
int chessboard[n][n];

// 保存解法的容器
vector<vector<int>> solutions;

// 检查当前格子上是否可以放置皇后
bool isValid(int row, int col) {
    // 检查同一列上是否有皇后
    for (int i = 0; i < row; i++) {
        if (chessboard[i][col] == 1)
            return false;
    }
    
    // 检查左上对角线上是否有皇后
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 1)
            return false;
    }
    
    // 检查右上对角线上是否有皇后
    for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 1)
            return false;
    }
    
    return true;
}

// 解决八皇后问题的递归函数
bool solveNQueens(int row) {
    // 如果已经遍历到最后一行，表示找到了一种解法，将当前棋盘状态保存下来
    if (row == n) {
        vector<int> solution;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (chessboard[i][j] == 1)
                    solution.push_back(j);
            }
        }
        solutions.push_back(solution);
        return true;
    }

    // 遍历当前行的每一个格子，尝试放置皇后
    for (int col = 0; col < n; col++) {
        // 如果当前格子满足放置皇后的条件，标记该格子为已占用
        if (isValid(row, col)) {
            chessboard[row][col] = 1;

            // 递归调用函数，遍历下一行
            solveNQueens(row + 1);

            // 如果递归调用的结果返回false，表示当前格子的放置方式不满足解法要求，回溯到上一步
            chessboard[row][col] = 0;
        }
    }

    return false;
}

// 打印解法
void printSolutions() {
    for (auto solution : solutions) {
        cout << "Solution:" << endl;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j == solution[i])
                    cout << "Q ";
                else
                    cout << ". ";
            }
            cout << endl;
        }
        cout << endl;
    }
}

int main() {
    solveNQueens(0);
    printSolutions();
    return 0;
}

このプログラムを実行すると、すべてのソリューションが出力されます。各ソリューションはチェッカーボードの形式で表示され、Q はクイーンを表し、. はスペースを表します。このアルゴリズムを使用すると、8 つのクイーン問題に対するすべての解を見つけることができます。

この記事が、C での Eight Queens 問題アルゴリズムの使用方法を理解するのに役立つことを願っています。このアルゴリズムを実装するには、再帰とバックトラッキングのアイデアを使用する必要がありますが、正しい手順に従う限り、8 クイーン問題の解決策を見つけることができます。

以上がC++ で Eight Queens 問題アルゴリズムを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。