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

C++实现八皇后问题

2023-06-30 01:04:20 深夜i -- --

C++ eight queens problem 棋盘问题回溯算法解决方案

八皇后问题是指在一个8×8的国际象棋棋盘上，放置8个皇后，使得任意两个皇后都不能在同一行、同一列或同一斜线上。这是一个经典的计算机科学问题，也是编程能力的一项考验。

C++语言是一种高级语言，具有可移植、高效、结构化等特点，非常适合用于解决算法问题。下面我们就来介绍一下如何使用C++语言实现八皇后问题。

首先，我们需要定义一个二维数组来表示棋盘，然后将其所有元素初始化为0，表示没有皇后。接着，我们从第一行开始逐行放置皇后，每放置一行皇后，就判断是否与前面的皇后冲突，若有冲突，则重新放置。直到最后一行放置完成，即得到一组合法的解。

具体的操作步骤如下：

1. 定义一个8×8的二维数组board，用于表示棋盘。

2. 编写一个放置皇后的函数place，该函数接受两个参数row和col，代表要放置皇后的行和列。在该函数中，首先判断该位置是否能放置皇后，如果冲突，则返回false；否则，在该位置放置皇后，并递归调用place函数放置下一行的皇后，直到所有皇后都放置完成。

3. 在主函数中，利用循环语句逐行放置皇后，放置完所有皇后后输出结果。

下面是C++代码的实现：

#include

using namespace std;

const int SIZE = 8; //棋盘大小

int board[SIZE][SIZE] = {0}; //棋盘

int count = 0; //记录解的数量

//判断该位置是否能放置皇后

bool check(int row, int col) {

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

if (board[i][col] == 1) //判断列是否有皇后

return false;

if (col-row+i >=0 && board[i][col-row+i] == 1) //判断左上对角线是否有皇后

return false;

if (col+row-i < SIZE && board[i][col+row-i] == 1) //判断右上对角线是否有皇后

return false;

}

return true; //没有冲突，可以放置皇后

}

//放置皇后

void place(int row) {

if (row == SIZE) { //已经放置了8个皇后，输出结果

count++;

cout << "Solution " << count << ":" << endl;

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

for (int j = 0; j < SIZE; j++) {

if (board[i][j] == 1)

cout << "Q ";

else

cout << "- ";

}

cout << endl;

}

cout << endl;

return;

}

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

if (check(row, i)) { //该位置可以放置皇后

board[row][i] = 1; //放置皇后

place(row+1); //递归放置下一行的皇后

board[row][i] = 0; //回溯，撤销皇后的位置

}

int main() {

place(0);

return 0;

}

以上代码实现了八皇后问题的解决方案。运行程序后，会输出所有的合法解（共92组）。通过这个例子，我们可以看到C++的强大，也深入理解了递归、回溯等算法的实现。

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

下一篇: C++常用框架汇总

评论区

()

相似文章