C++实现八皇后问题的代码 |21xrx.com

C++实现八皇后问题的代码

2023-07-06 00:42:44 深夜i 11 0

C++ 八皇后问题代码

八皇后问题是一道经典的算法问题，它的解决方法可以用于很多场景中。在计算机科学中，我们可以使用C++语言来实现八皇后问题，下面是代码实现的方法。

代码实现：

在C++中，我们可以使用递归函数来解决八皇后问题。具体实现如下：

#include <iostream>
using namespace std;
// 定义棋盘
int board[8][8];
// 检查该位置是否可以放置皇后
bool isSafe(int row, int col) {
  // 检查左上方
  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 < 8; i--, j++)
    if (board[i][j])
      return false;  
  
  // 检查上方
  for (int i = row; i >= 0; i--)
    if (board[i][col])
      return false;  
      
  return true;
}
// 求解八皇后问题
bool solve(int row) {
  // 所有皇后均已放置
  if (row == 8)
    return true;
  for (int col = 0; col < 8; col++) {
    // 检查该位置是否可以放置皇后
    if (isSafe(row, col)) {
      // 放置皇后
      board[row][col] = 1;
      
      // 递归求解下一行
      if (solve(row + 1))
        return true;
      // 撤销上一步
      board[row][col] = 0;
    }
  }
  // 无解
  return false;
}
// 打印棋盘
void printBoard() {
  for (int i = 0; i < 8; i++) {
    for (int j = 0; j < 8; j++) {
      if (board[i][j] == 1)
        cout << "Q";
      else
        cout << ".";
    }
    cout << endl;
  }
}
int main() {
  if (solve(0)) {
    printBoard();
  } else
    cout << "No solution" << endl;
  
}

代码解析：

我们可以先定义一个8 * 8的二维数组`board`表示棋盘，每个元素如果为1表示该格子上有皇后，为0则表示没有皇后。

我们可以使用`isSafe`函数来检查某个位置是否可以放置皇后。该函数分别检查了左上方、右上方和正上方是否有皇后，如果有则返回false，否则返回true。

在`solve`函数中，我们使用递归来求解八皇后问题。对于每一行，我们依次遍历该行的每一列，检查该位置是否可以放置皇后。如果可以，我们则将该位置置为1，进入下一行的递归。如果递归成功，表示该方式可行，返回true；否则，我们撤销该位置的皇后，继续检查下一列。

在`printBoard`函数中，我们可以遍历棋盘中的所有元素并打印，将棋盘输出。

在`main`函数中，我们首先调用`solve`函数求解八皇后问题，如果有解则调用`printBoard`函数输出棋盘，否则输出"No solution"。

总结：

通过使用递归函数和二维数组，我们可以轻松地解决八皇后问题。这个过程中可以看到，C++语言能够很好地实现算法问题，我们只需要理解问题本身及其解决思路，运用语言的基本语法和数据结构即可编写出高效的代码。

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

下一篇: Node.js工程化实践

评论区

相似文章