C++ N皇后问题输出方案个数 |21xrx.com

2023-07-11 00:51:04 深夜i -- --

C++ N皇后问题方案输出数量

N皇后问题是经典的回溯算法问题，它需要在N×N的棋盘上摆放N个皇后，使得每个皇后都不能相互攻击（即不在同一行、同一列、同一对角线上）。对于这个问题，我们需要输出所有的解决方案个数。接下来，我们将使用C++语言来实现这个问题。

首先，我们需要定义一个函数check，其作用是判断当前位置是否可以放置皇后，如果可以，就返回true，否则返回false。在这个函数中，我们需要分别对当前行、当前列、当前对角线进行判断，如果存在冲突，就返回false。具体实现如下：

bool check(int row, int col, int n, vector & board) {

for (int i = 0; i < row; i++) {

if (board[i][col] == 'Q') return false; // 当前列存在皇后则直接返回false

}

for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {

if (board[i][j] == 'Q') return false; // 左上角存在皇后则直接返回false

}

for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {

if (board[i][j] == 'Q') return false; // 右上角存在皇后则直接返回false

}

return true; // 否则，返回true

}

接下来，我们需要定义一个递归函数solve，其作用是在棋盘上逐行放置皇后，当放置完成时，将当前方案个数加一。这个函数包括两个参数，分别是当前行数和棋盘对象。具体实现如下：

void solve(int row, int n, vector & board, int& count) {

if (row == n) { // 如果已经放置完成，则将方案个数加一并返回

count++;

return;

}

for (int col = 0; col < n; col++) { // 逐列放置皇后，并判断是否冲突

if (check(row, col, n, board)) {

board[row][col] = 'Q'; // 放置皇后

solve(row + 1, n, board, count); // 递归到下一行

board[row][col] = '.'; // 回溯至上一步，移除皇后

}

最后，我们只需要调用solve函数即可得到所有解决方案的个数。具体实现如下：

int totalNQueens(int n) {

vector board(n, string(n, '.')); // 创建一个n×n的棋盘

int count = 0; // 方案个数初始化为0

solve(0, n, board, count); // 从第一行开始递归

return count; // 返回方案个数

}

综上所述，我们可以使用C++语言来解决N皇后问题，并输出所有解决方案的个数。这个问题是一个经典的回溯算法问题，在工程中也有广泛的应用。通过这个问题，我们可以加深对回溯算法的理解，并提高编程能力。

上一篇: idea打包java可执行jar包

下一篇: C++ 网络编程

()

相似文章