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

C++实现皇后问题

2023-07-06 22:09:06 深夜i -- --

C++ 皇后问题 N皇后问题回溯算法解决方案

在计算机科学中，八皇后问题是一个经典的问题。问题的目标是将八个皇后放在一个8 × 8的国际象棋棋盘上，使得任何一个皇后都不能被另一个皇后吃掉。该问题的解决方案在计算机科学领域中有很多应用，尤其是在人工智能领域中。

C++是一种流行的编程语言，可以用它来实现解决八皇后问题。首先，我们需要设计程序的算法，然后用C++实现它。

算法的核心是递归回溯。我们从第一行开始，逐行放置皇后。在放置每个皇后之前，我们检查该皇后是否能被“攻击”，如果可以被攻击，我们就尝试在该行的下一个位置放置皇后。如果没有下一个位置了，我们就回溯到前一行，将之前放置的皇后移到该行的下一个位置，然后继续尝试下一个位置。

以下是C++实现代码：


#include <iostream>
using namespace std;
const int n = 8;
int board[n][n] = {0}; // 棋盘
/* 检查皇后是否被攻击 */
bool check(int row, int col) {
  for(int i=0; i<n; i++) {
    if(board[row][i] || board[i][col]) // 同一行或同一列
      return false;
    
    if(row+i<n && col+i<n && board[row+i][col+i]) // 右下方向
      return false;
    
    if(row-i>=0 && col+i<n && board[row-i][col+i]) // 右上方向
      return false;
    
    if(row+i<n && col-i>=0 && board[row+i][col-i]) // 左下方向
      return false;
    
    if(row-i>=0 && col-i>=0 && board[row-i][col-i]) // 左上方向
      return false;
    
  }
  return true;
}
/* 放置皇后 */
bool place(int row) {
  if(row == n) // 找到解决方案
    return true;
  
  for(int i=0; i<n; i++) {
    if(check(row, i)) { // 可以放置皇后
      board[row][i] = 1;
      if(place(row+1)) // 放置下一个
        return true;
      
      board[row][i] = 0; // 回溯
    }
  }
  return false;
}
/* 打印解决方案 */
void printBoard() {
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      cout << board[i][j] << " ";
    }
    cout << endl;
  }
}
int main() {
  if(place(0)) { // 从第一行开始
    printBoard();
  } else
    cout << "No solution" << endl;
  
  return 0;
}

在主函数中，我们从第一行开始放置皇后。如果找到解决方案，就打印棋盘；否则，显示“无解”。

使用以上C++代码，我们可以在控制台上看到输出结果，显示放置皇后的坐标。实现了该问题，可以在人工智能相关的应用中使用了。

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

下一篇: C++之父的简介

评论区

()

相似文章