Home Backend Development C++ How to use the Eight Queens Problem algorithm in C++

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

Sep 19, 2023 pm 12:07 PM
c++ algorithm Eight Queens

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!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undress AI Tool

Undress AI Tool

Undress images for free

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Hot Topics

PHP Tutorial
1488
72
What is high-frequency virtual currency trading? The principles and technical implementation points of high-frequency trading What is high-frequency virtual currency trading? The principles and technical implementation points of high-frequency trading Jul 23, 2025 pm 11:57 PM

High-frequency trading is one of the most technologically-rich and capital-intensive areas in the virtual currency market. It is a competition about speed, algorithms and cutting-edge technology that ordinary market participants are hard to get involved. Understanding how it works will help us to have a deeper understanding of the complexity and specialization of the current digital asset market. For most people, it is more important to recognize and understand this phenomenon than to try it yourself.

Explain RAII in C Explain RAII in C Jul 22, 2025 am 03:27 AM

RAII is an important technology used in resource management in C. Its core lies in automatically managing resources through the object life cycle. Its core idea is: resources are acquired at construction time and released at destruction, thereby avoiding leakage problems caused by manual release. For example, when there is no RAII, the file operation requires manually calling fclose. If there is an error in the middle or return in advance, you may forget to close the file; and after using RAII, such as the FileHandle class encapsulates the file operation, the destructor will be automatically called after leaving the scope to release the resource. 1.RAII is used in lock management (such as std::lock_guard), 2. Memory management (such as std::unique_ptr), 3. Database and network connection management, etc.

C   vector get first element C vector get first element Jul 25, 2025 am 12:35 AM

There are four common methods to obtain the first element of std::vector: 1. Use the front() method to ensure that the vector is not empty, has clear semantics and is recommended for daily use; 2. Use the subscript [0], and it also needs to be judged empty, with the performance comparable to front() but slightly weaker semantics; 3. Use *begin(), which is suitable for generic programming and STL algorithms; 4. Use at(0), without manually null judgment, but low performance, and throw exceptions when crossing the boundary, which is suitable for debugging or exception handling; the best practice is to call empty() first to check whether it is empty, and then use the front() method to obtain the first element to avoid undefined behavior.

How to develop AI-based text summary with PHP Quick Refining Technology How to develop AI-based text summary with PHP Quick Refining Technology Jul 25, 2025 pm 05:57 PM

The core of PHP's development of AI text summary is to call external AI service APIs (such as OpenAI, HuggingFace) as a coordinator to realize text preprocessing, API requests, response analysis and result display; 2. The limitation is that the computing performance is weak and the AI ecosystem is weak. The response strategy is to leverage APIs, service decoupling and asynchronous processing; 3. Model selection needs to weigh summary quality, cost, delay, concurrency, data privacy, and abstract models such as GPT or BART/T5 are recommended; 4. Performance optimization includes cache, asynchronous queues, batch processing and nearby area selection. Error processing needs to cover current limit retry, network timeout, key security, input verification and logging to ensure the stable and efficient operation of the system.

C   bit manipulation example C bit manipulation example Jul 25, 2025 am 02:33 AM

Bit operation can efficiently implement the underlying operation of integers, 1. Check whether the i-th bit is 1: Use n&(1

C   Standard Library Explained C Standard Library Explained Jul 25, 2025 am 02:11 AM

The C standard library helps developers improve code quality by providing efficient tools. 1. STL containers should be selected according to the scene, such as vector suitable for continuous storage, list suitable for frequent insertion and deletion, and unordered_map is suitable for fast search; 2. Standard library algorithms such as sort, find, and transform can improve efficiency and reduce errors; 3. Intelligent pointers unique_ptr and shared_ptr effectively manage memory to avoid leakage; 4. Other tools such as optional, variant, and function enhance code security and expressiveness. Mastering these core functions can significantly optimize development efficiency and code quality.

C   function example C function example Jul 27, 2025 am 01:21 AM

Functions are the basic unit of organizing code in C, used to realize code reuse and modularization; 1. Functions are created through declarations and definitions, such as intadd(inta,intb) returns the sum of the two numbers; 2. Pass parameters when calling the function, and return the result of the corresponding type after the function is executed; 3. The function without return value uses void as the return type, such as voidgreet(stringname) for outputting greeting information; 4. Using functions can improve code readability, avoid duplication and facilitate maintenance, which is the basic concept of C programming.

Understanding the C   ABI Understanding the C ABI Jul 24, 2025 am 01:23 AM

C ABI is the underlying rule that the compiler follows when generating binary code, which determines mechanisms such as function calls, object layout, name adaptation, etc. 1. It ensures that different compilation units interact correctly, 2. Different compilers or versions may adopt different ABIs, affecting dynamic library links, STL transfers, virtual function calls, etc. 3. Cross-platform development, long-term system maintenance, third-party library use and other scenarios need to pay special attention to ABI consistency, 4. ABI can be controlled through macro definitions and compilation options, and use tools to view the symbol table to judge consistency.

See all articles