21xrx.com
2024-11-05 17:22:11 Tuesday
登录
文章检索 我的文章 写文章
C++实现八皇后问题的代码
2023-07-06 00:42:44 深夜i     --     --
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++语言能够很好地实现算法问题,我们只需要理解问题本身及其解决思路,运用语言的基本语法和数据结构即可编写出高效的代码。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复