n皇后问题

tech2024-12-04  7

深搜讲点题目二 八皇后 题目描述 请编一个程序找出所有棋子放置的解。 并把它们以上面的序列方法输出,解按字典顺序排列。 请输出前 3 个解。最后一行是解的总个数。 输入格式 一行一个正整n,表示棋盘是 n×n 大小的。 输出格式 前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。 输入样列

6

输出样列

2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4

基本思路 1 一个输出函数 只输出前三个解和解数 2 一个判断是否越界函数 3 一个搜索函数 4 一个主函数 代码如下

#include<iostream> #include<string> using namespace std; int n,ans,a[1001],b[1001],c[1001],d[1001]; //n 表示方阵大小 //ans 表示解的总数 //a 表示行数组 //b 表示纵数组 //c 表示对角线右上 和左下 //d 表示对角线左上 和右下 void print() { if(ans<=2) //只输出前面的三个解,后面的就不输出了 但是ans还是在递增 { for(int k=1;k<=n;k++) cout<<a[k]<<" "; cout<<endl; } ans++; return ; } int check(int i,int j) { return !b[j]&&!c[i+j]&&!d[i-j+n]; } void dfs(int i) { if(i>n) { print(); return ; } else { for(int j=1;j<=n;j++){ if (check(i,j)){ //做标记 表示这个坐标有皇后了 a[i]=j; // 表示第i行的位置 b[j]=1; c[i+j]=1; d[i-j+n]=1; dfs(i+1); //搜索下一个皇后 b[j]=0; //将上一个皇后的位置取消标记 c[i+j]=0; d[i-j+n]=0; //回到上一步 清楚标记 } } } } int main(){ cin>>n; dfs(1); cout<<ans; return 0; }
最新回复(0)