信息学社团邀请你解决八皇后问题

// 八皇后问题回溯求解 #include <iostream> #include <vector> using namespace std; // 存储所有解 vector<vector<string>> solutions; // 检查当前位置是否可以放置皇后 bool isValid(int row, int col, vector<int>& cols) { for (int i = 0; i < row; i++) { // 检查列冲突或对角线冲突 if (cols[i] == col || abs(i - row) == abs(cols[i] - col)) { return false; } } return true; } // 回溯求解 void backtrack(int row, vector<int>& cols) { // 找到一个解 if (row == 8) { vector<string> board; for (int i = 0; i < 8; i++) { string line(8, '.'); line[cols[i]] = 'Q'; board.push_back(line); } solutions.push_back(board); return; } // 尝试在当前行的每一列放置皇后 for (int col = 0; col < 8; col++) { if (isValid(row, col, cols)) { cols[row] = col; // 放置皇后 backtrack(row + 1, cols); // 递归下一行 cols[row] = -1; // 回溯，移除皇后 } } } // 主函数 int main() { vector<int> cols(8, -1); backtrack(0, cols); cout << "八皇后问题共有" << solutions.size() << "种解" << endl; return 0; }