How to use the Eight Queens Problem algorithm in C++

How to use the eight queens problem algorithm in C

The eight queens problem is a classic algorithm problem that requires placing eight queens on an 8x8 chessboard such that any No two queens can attack each other, that is, any two queens cannot be in the same row, column, or diagonal. There are many algorithms to solve the Eight Queens Problem, one of the common methods is to use the backtracking algorithm. This article will introduce how to use C language to implement the algorithm of the Eight Queens Problem and provide specific code examples.

First, we need to define an 8x8 chessboard, represented by a two-dimensional array. Each element of the array can represent a chessboard grid, 1 means there is a queen on the grid, 0 means there is no queen.

Next, we define a recursive function to go through each row of the board and try to place the queen. The specific steps are as follows:

1. If you have traversed to the last row of the chessboard, it means you have found a solution, save the current chessboard state, and return.
2. Traverse each grid in the current row and try to place the queen.
3. If the current grid does not meet the conditions for placing the queen (that is, it conflicts with the already placed queen), the current grid will be skipped and the next grid will continue to be traversed.
4. If the current grid meets the conditions for placing a queen, place a queen on the grid and mark the grid as occupied.
5. Call the function recursively and traverse the next line.
6. If the result of the recursive call returns true, it means that a solution has been found, then the solution will be saved and true will be returned.
7. If the result of the recursive call returns false, it means that the placement of the current grid does not meet the solution requirements, then remove the queen on the grid and go back to the previous step.

Based on the above ideas, we can implement the following code:

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

Running this program will output all solutions. Each solution is displayed in the form of a checkerboard, where Q represents the queen and . represents the space. With this algorithm, we can find all solutions to the Eight Queens Problem.

I hope this article will help you understand how to use the Eight Queens Problem algorithm in C. Implementing this algorithm requires the use of recursion and backtracking ideas. As long as you follow the correct steps, you can find the solution to the Eight Queens Problem.

The above is the detailed content of How to use the Eight Queens Problem algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!