Comment utiliser l'algorithme du problème des huit reines en C++

Comment utiliser l'algorithme du problème des huit reines en C++

Le problème des huit reines est un problème d'algorithme classique qui nécessite de placer huit reines sur un échiquier 8x8 afin qu'aucune deux reines ne puisse s'attaquer, c'est-à-dire deux reines quelconques ne peut pas être dans la même ligne, colonne ou diagonale. Il existe de nombreux algorithmes pour résoudre le problème des huit reines, l'une des méthodes courantes consiste à utiliser l'algorithme de backtracking. Cet article présentera comment utiliser le langage C++ pour implémenter l'algorithme du problème des huit reines et fournira des exemples de code spécifiques.

Tout d'abord, nous devons définir un échiquier 8x8, représenté par un tableau bidimensionnel. Chaque élément du tableau peut représenter une grille d'échiquier, 1 signifie qu'il y a une reine sur la grille, 0 signifie qu'il n'y a pas de reine.

Ensuite, nous définissons une fonction récursive pour parcourir chaque ligne du plateau et essayer de placer la reine. Les étapes spécifiques sont les suivantes :

1. Si vous avez atteint la dernière ligne de l'échiquier, cela signifie que vous avez trouvé une solution, enregistrez l'état actuel de l'échiquier et revenez.
2. Parcourez chaque grille de la rangée actuelle et essayez de placer la reine.
3. Si la grille actuelle ne remplit pas les conditions de placement de la reine (c'est-à-dire qu'elle entre en conflit avec la reine déjà placée), la grille actuelle sera ignorée et la grille suivante continuera à être parcourue.
4. Si la grille actuelle remplit les conditions pour placer une reine, placez une reine sur la grille et marquez la grille comme occupée.
5. Appelez la fonction de manière récursive et parcourez la ligne suivante.
6. Si le résultat de l'appel récursif renvoie vrai, cela signifie qu'une solution a été trouvée, alors la solution sera enregistrée et vrai sera renvoyé.
7. Si le résultat de l'appel récursif renvoie faux, cela signifie que le placement de la grille actuelle ne répond pas aux exigences de la solution, alors retirez la reine de la grille et revenez à l'étape précédente.

Sur la base des idées ci-dessus, nous pouvons implémenter le code suivant :

#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;
}

Exécutez ce programme et toutes les solutions seront affichées. Chaque solution est affichée sous la forme d'un damier, où Q représente la reine et . Avec cet algorithme, nous pouvons trouver toutes les solutions au problème des huit reines.

J'espère que cet article vous aidera à comprendre comment utiliser l'algorithme Eight Queens Problem en C++. La mise en œuvre de cet algorithme nécessite l'utilisation d'idées de récursion et de retour en arrière. Tant que vous suivez les bonnes étapes, vous pouvez trouver la solution au problème des huit reines.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!