21xrx.com
2024-06-03 04:48:07 Monday
登录
文章检索 我的文章 写文章
C++算法实现八皇后问题
2023-07-14 03:33:37 深夜i     --     --
C++ 算法 实现 八皇后问题

八皇后问题是一个经典的数学问题,也是计算机科学领域中的一个经典问题。它的目标是将八个皇后放在一个8×8的棋盘上,使得每个皇后都无法攻击到另一个。

通过使用C++算法,我们可以快速有效地解决这个问题。下面是一个简单的C++实现的八皇后问题的例子:


#include<iostream>

using namespace std;

#define n 8

int q[n], cou = 0;

int abs_(int a){

  return a < 0 ? -a : a;

}

bool check(int i, int j){

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

    if (q[l] == j || abs_(l - i) == abs_(q[l] - j)) return false;

  }

  return true;

}

void try_(int i){

  if (i == n){

    cou++;

    return;

  }

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

    if (check(i, j)){

      q[i] = j;

      try_(i + 1);

    }

  }

}

int main(){

  try_(0);

  cout << cou << endl;

  return 0;

}

这个算法使用了递归的思想,从第一个皇后开始,逐个尝试将皇后放在每一行的每个位置。如果当前的位置是安全的,就将皇后放在这里,然后尝试下一行。如果这个皇后放在最后一行了,说明我们找到了一种符合要求的解法,就将计数器加1。

其中,check函数用来检查这个位置是否可以放置皇后。如果这个位置的同一列或者左上到右下或者右上到左下的对角线上已经有一个皇后了,那么就不能再放这里了。

最后,主函数将开始调用try函数,并输出计数器的值,表示符合要求的方案数量。

通过上面这个简单的C++算法实现,我们可以有效地解决八皇后问题,并且针对不同规模的问题,只需要对常量n进行相应的修改即可。

  
  

评论区

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