C++ 8퀸 문제

1 개요

C++ 8퀸 문제

C++

Copy

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int N = 8;
int solutionCount = 0;

// 현재까지 배치된 퀸들이 안전한지 검사하는 함수
bool isSafe(const vector<int>& board, int row, int col) {
    for (int i = 0; i < row; i++) {
        // 같은 열에 있거나 대각선에 있으면 충돌
        if (board[i] == col || abs(board[i] - col) == abs(i - row))
            return false;
    }
    return true;
}

// row번째 행에 퀸을 배치하는 재귀 함수
void solve(vector<int>& board, int row) {
    if (row == N) {
        // 해답 출력
        solutionCount++;
        cout << "Solution " << solutionCount << ":\n";
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i] == j)
                    cout << "Q ";
                else
                    cout << ". ";
            }
            cout << "\n";
        }
        cout << "\n";
        return;
    }
    // 현재 행의 각 열에 대해 검사
    for (int col = 0; col < N; col++) {
        if (isSafe(board, row, col)) {
            board[row] = col;   // 퀸 배치
            solve(board, row + 1); // 다음 행으로 이동
        }
    }
}

int main() {
    vector<int> board(N, -1); // board[i]는 i번째 행에 배치된 퀸의 열 번호를 저장
    solve(board, 0);
    cout << "Total solutions: " << solutionCount << endl;
    return 0;
}

2 같이 보기

• 8퀸 문제