C++求解八皇后问题 |21xrx.com

C++求解八皇后问题

2023-06-27 07:39:04 深夜i -- --

C++ 求解八皇后问题

八皇后问题是一个经典的数学问题，其目的是在棋盘上安置八个皇后，使得它们互相攻击的可能性最小化。这个问题在计算机科学领域中受到广泛关注，因为它是一个良好的展示回溯算法的例子。在这篇文章中，我们将介绍如何使用C++编写一个简单的程序来解决八皇后问题。

首先，我们需要定义一个棋盘。我们可以使用一个二维布尔数组来表示棋盘，其中每个位置表示一个方格是否被占用。同时，我们还需要一个变量来记录已经放置的皇后数量。代码如下：

bool board[8][8];

int queens_placed = 0;

接下来，我们需要定义一个函数来检查新的皇后是否可以安全地放置在棋盘上。这个函数需要检查这个位置是否与已经放置的皇后位置有冲突。我们可以分别检查同一行、同一列和两条对角线上的位置是否有皇后。如果该位置为空闲，且不与已经放置的皇后位置有冲突，就返回真；否则返回假。代码如下：

bool is_safe(int row, int col) {

// check horizontally

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

if (board[row][i]) return false;

}

// check vertically

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

if (board[i][col]) return false;

}

// check diagonal 1

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 < 8 && j < 8; ++i, ++j) {

if (board[i][j]) return false;

}

// check diagonal 2

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

if (board[i][j]) return false;

}

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

if (board[i][j]) return false;

}

// safe location

return true;

}

接下来，我们需要定义一个递归函数来尝试放置一个皇后。这个函数会尝试在每一行中放置一个皇后。如果可以放置，则继续尝试放置下一个皇后；如果不能放置，则回溯到上一个皇后位置并尝试其他位置。如果成功放置八个皇后，则结束并返回真。代码如下：

bool place_queen(int row) {

if (queens_placed == 8) return true;

for (int col = 0; col < 8; ++col) {

if (is_safe(row, col)) {

board[row][col] = true;

++queens_placed;

if (place_queen(row + 1)) return true;

board[row][col] = false;

--queens_placed;

}

return false;

}

最后，我们只需要在主函数中调用place_queen函数来尝试放置所有的皇后。如果成功放置，则输出棋盘，否则输出失败信息。代码如下：

int main() {

if (place_queen(0)) {

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

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

if (board[i][j]) cout << "Q ";

else cout << ". ";

}

cout << endl;

}

} else

cout << "Failed to place the queens" << endl;

return 0;

}

总结：这是C++程序解决八皇后问题的简单实现，使用了回溯算法，以及用二维布尔数组记录棋盘当前状态。通过逐步放置皇后并检查安全性的方式来解决问题，利用递归函数和回溯机制来完成任务。

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

下一篇: 《C++从入门到精通第五版PDF》

评论区

()

相似文章