설명

• Backtracking
• 해를 찾는 도중, 현재 경로가 유망하지 않으면 되돌아가서 다른 경로를 탐색하는 기법
• 가능한 모든 경우의 수를 탐색하되, 불필요한 경로는 조기에 차단
• N-Queens, 미로 찾기, 부분 집합 합

예제

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

bool isSafe(vector<string>& board, int row, int col) {
    int n = board.size();
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') {
            return false;
        }
    }

    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') {
            return false;
        }
    }

    for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q') {
            return false;
        }
    }

    return true;
}

void solveNQueens(vector<string>& board, int row, vector<vector<string>>& solutions) {
    if (row == board.size()) {
        solutions.push_back(board);
        return;
    }

    for (int col = 0; col < board.size(); col++) {
        if (isSafe(board, row, col)) {
            board[row][col] = 'Q';
            solveNQueens(board, row + 1, solutions);
            board[row][col] = '.';
        }
    }
}

vector<vector<string>> nQueens(int n) {
    vector<vector<string>> solutions;
    vector<string> board(n, string(n, '.'));
    solveNQueens(board, 0, solutions);
    return solutions;
}

int main() {
    int n = 4;
    vector<vector<string>> solutions = nQueens(n);

    for (auto& solution : solutions) {
        for (auto& row : solution) {
            cout << row << "\n";
        }
        cout << "\n";
    }

    return 0;
}

결과

• . Q . .
  . . . Q
  Q . . .
  . . Q .

---

• . . Q .
  Q . . .
  . . . Q
  . Q . .

---

설명

1. 빈 체스판 준비
2. 첫 번째 행부터 시작하여 각 행마다 퀸 배치
3. 각 행에 퀸 배치시, 안전한지 검사
4. 안전하면 퀸 배치, 다음행으로 이동
5. 다음 행에서 다시 퀸 배치 가능한지 검사
6. 특정 행에 퀸 배치 불가시, 이전 행으로 돌아가 다른 위치에 퀸 배치(백트래킹)
7. 모든 행에 퀸 배치 가능하면 하나의 해 발견
8. 모든 해 찾을 때까지 과정 반복