C++에서 Eight Queens 문제 알고리즘을 사용하는 방법

C++에서 8개의 퀸 문제 알고리즘을 사용하는 방법

8개의 퀸 문제는 두 개의 퀸이 서로 공격할 수 없도록 8x8 체스판에 8개의 퀸을 배치해야 하는 고전적인 알고리즘 문제입니다. 같은 행, 열 또는 대각선에 있을 수 없습니다. Eight Queens 문제를 해결하는 알고리즘에는 여러 가지가 있으며, 일반적인 방법 중 하나는 역추적 알고리즘을 사용하는 것입니다. 이 기사에서는 C++ 언어를 사용하여 Eight Queens 문제의 알고리즘을 구현하는 방법을 소개하고 구체적인 코드 예제를 제공합니다.

먼저 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는 퀸을 나타내고 는 공간을 나타냅니다. 이 알고리즘을 사용하면 여덟 여왕 문제에 대한 모든 해결책을 찾을 수 있습니다.

이 기사가 C++에서 Eight Queens Problem 알고리즘을 사용하는 방법을 이해하는 데 도움이 되기를 바랍니다. 이 알고리즘을 구현하려면 재귀 및 역추적 아이디어를 사용해야 합니다. 올바른 단계를 따르면 여덟 여왕 문제에 대한 해결책을 찾을 수 있습니다.

위 내용은 C++에서 Eight Queens 문제 알고리즘을 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!