8皇后问题有多少解,用c++编写一个程序并输出答案
时间: 2024-04-15 21:30:50 浏览: 14
8皇后问题是一个经典的问题,要求在一个8x8的棋盘上放置8个皇后,使得任意两个皇后都不在同一行、同一列或同一对角线上。这个问题的解有92种。
以下是一个使用C++编写的程序来解决8皇后问题,并输出所有解:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 检查当前位置是否可以放置皇后
bool isSafe(vector<int>& board, int row, int col) {
// 检查同一列是否有其他皇后
for (int i = 0; i < row; i++) {
if (board[i] == col) {
return false;
}
}
// 检查左上对角线是否有其他皇后
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i] == j) {
return false;
}
}
// 检查右上对角线是否有其他皇后
for (int i = row, j = col; i >= 0 && j < board.size(); i--, j++) {
if (board[i] == j) {
return false;
}
}
return true;
}
// 递归函数来求解8皇后问题
void solveNQueens(vector<vector<int>>& solutions, vector<int>& board, int row) {
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;
solveNQueens(solutions, board, row + 1);
}
}
}
// 输出解集
void printSolutions(vector<vector<int>>& solutions) {
for (int i = 0; i < solutions.size(); i++) {
cout << "Solution #" << i + 1 << ":\n";
for (int j = 0; j < solutions[i].size(); j++) {
for (int k = 0; k < solutions[i].size(); k++) {
if (solutions[i][j] == k) {
cout << "Q ";
} else {
cout << ". ";
}
}
cout << endl;
}
cout << endl;
}
}
int main() {
vector<vector<int>> solutions;
vector<int> board(8, -1);
solveNQueens(solutions, board, 0);
cout << "Total solutions: " << solutions.size() << endl;
printSolutions(solutions);
return 0;
}
```
这个程序使用回溯法来解决8皇后问题。它首先定义了一个函数 `isSafe` 来检查当前位置是否可以放置皇后,然后定义了一个递归函数 `solveNQueens` 来求解问题,并将所有解存储在一个二维向量 `solutions` 中。最后,程序输出解的数量和每个解的具体情况。
你可以运行这个程序来获得所有的解。希望对你有帮助!