八皇后问题
在国际象棋中, 皇后是最强大的一枚棋子, 可以吃掉与其在同一行, 列和斜线的敌方棋子. 将八个皇后摆在一张 8*8 的国际象棋棋盘上, 使每个皇后都无法吃掉别的皇后, 一共有多少种摆法?
程序实现
程序摘自回溯法与八皇后问题 https://www.cnblogs.com/bigmoyan/p/4521683.html
- #include<iostream>
- #include<math.h>
- using namespace std;
- int n=8;
- int total=0;
- int *c=new int(n); // 下标为行数, 存的数为列数
- bool is_ok(int row){
- for(int j=0;j!=row;j++){
- if(c[row]==c[j] || // 检测是否在同一列
- row-c[row]==j-c[j] || // 检测是否在同一 "\" 斜线上
- row+c[row]==j+c[j]) // 检测是否在同一 "/" 斜线上
- return false;
- }
- return true;
- }
- void queen(int row){
- if(row==n)
- total++;
- else
- for(int col=0;col!=n;col++){
- c[row]=col;
- if(is_ok(row))
- queen(row+1);
- }
- }
- int main(){
- queen(0);
- cout<<total;
- return 1;
- }
来源: http://www.bubuko.com/infodetail-2754086.html