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

#include  #include  using namespace std; const int n = 8; // 棋盘大小 // 棋盘 int chessboard[n][n]; // 保存解法的容器 vector> 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 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; }