八皇后问题代码 c++
时间: 2024-08-16 07:08:45 浏览: 35
八皇后问题是一个经典的回溯算法问题,目标是在一个8x8的棋盘上放置8个皇后,使得任意两个皇后都不在同一行、同一列或对角线上。下面是使用 C++ 编程解决八皇后问题的一个简单版本:
```cpp
#include <iostream>
#include <vector>
// 定义一个函数用于检查某行、列和对角线是否已经有皇后
bool isSafe(int row, int col, std::vector<std::vector<bool>>& board) {
// 检查当前行是否有皇后
if (board[row][col])
return false;
// 检查左上方对角线是否有皇后
for (int i = 0; i < row; i++)
if (board[i][col - i])
return false;
// 检查右上方对角线是否有皇后
for (int i = 0; i < row; i++)
if (board[i][col + i])
return false;
return true;
}
// 回溯函数,尝试在给定位置放置皇后
void solveNQueens(std::vector<std::vector<bool>>& board, int row, int& solutions) {
if (row == 8) { // 如果放置完所有皇后,解决方案增加
solutions++;
return;
}
// 对于每一列尝试放置皇后
for (int col = 0; col < 8; col++) {
if (isSafe(row, col, board)) { // 如果当前位置安全,放置皇后并继续下一行
board[row][col] = true;
solveNQueens(board, row + 1, solutions);
board[row][col] = false; // 取消放置,回溯到前一步
}
}
}
int main() {
std::vector<std::vector<bool>> board(8, std::vector<bool>(8, false)); // 初始化空棋盘
int solutions = 0; // 记录解的数量
solveNQueens(board, 0, solutions); // 开始搜索
std::cout << "八皇后问题有 " << solutions << " 种解法。\n";
return 0;
}
```