8 solutions
-
11
#include <bits/stdc++.h> using namespace std; int num = 0; int a[8][8]; int notDanger(int x, int y) { int i, j; // 判断列方向 for( i=0; i < 8; i++) { if( a[i][y]==1) { return 0; } } // 判断左对角线 for( i=x, j=y; i>=0 && j>=0; i--, j--) { if(a[i][j]==1) { return 0; } } // 判断右对角线 for( i=x, j=y; i>=0 && j<8; i--, j++) { if(a[i][j]==1) { return 0; } } return 1; } void Print()//打印结果 { int x, y; printf("No. %d\n", num+1); for(x=0; x < 8; x++) { for(y=0; y < 8; y++) { if(a[y][x]==1/*要a[y][x]!不能a[x][y]!*/) { printf("1 "); } else { printf("0 "); } } printf("\n"); } printf("\n"); } void EightQueen(int x) { int y; if(x==8)//如果遍历完八行都找到放置皇后的位置则打印 { Print();//打印八皇后的解 num++; return; } for(y=0; y < 8; y++)//回溯，递归 { if(notDanger(x, y))// 判断是否危险 { a[x][y]=1;//有皇后 EightQueen(x+1);//回溯 a[x][y]=0;//清零 } } } int main() { EightQueen(0); return 0; } -
5
C23linboming LV 6 @ 2024-1-24 10:14:43
AC呆马：（请笑纳）
#include <iostream> #include <cmath> using namespace std; int n; int x[100000]; int cnt; bool place(int t) { for(int j = 1; j < t; j++) { if(x[t] == x[j] || t - j == abs(x[t] - x[j])) return false; } return true; } void backtrack(int t) { if(t > n) { cnt++; cout << "No. " << cnt << endl; for(int j = 1; j<= n; j++) { for(int i = 1; i <= n; i++) cout << ((x[i] == j) ? 1 : 0) << " "; cout << endl; } return; } for(int i = 1; i<= n; i++) { x[t] = i; if(place(t)) backtrack(t+1); } } int main() { n = 8; cnt = 0; backtrack(1); return 0; } ```* # 制作不易，一键点赞，谢谢**-
C23panweiming
@ 2024-3-5 19:06:57
屎
-
C23huangminzhe @ 2024-3-5 19:09:48
-
-
1
C23huangyuran
LV 8
@ 2024-3-8 13:51:21
题意
输出所有八皇后的解
死路
二维数组地图式写法（也可以AC，但不是最优解）。
缺点：每次判断都要遍历，空间、时间大。
思路
三个vis数组，存列与对角线的不可填状态。列不用说，左至右对角线下标表示行列差值（差值相同同一对角线），右至左对角线下标表示行列和（同理）。至于下标表示自己做题时要会推理。
代码
#include<iostream> using namespace std; int n;//存输出次数 int a[9]; bool vis[8],vlr[17],vrl[17];//vlr从左往右，vrl相反，vis是列 void print();//发送图片[狗头] void dfs(int);//真正的主函数 bool f(int,int);//判断函数 void set(int,int,bool);//承担标记与回溯的双重函 int main(){ dfs(1);//简介的main函数 } void print(){ n++; cout<<"No. "<<n<<"\n";//有空格，坑了潘伟明一把，但我觉得有点空，拿鼠标找了一下，果然有空格 for(int i=1;i<9;i++){ for(int j=1;j<9;j++) if(a[j]==i)//见提示 cout<<"1 "; else cout<<"0 "; cout<<"\n"; } } void dfs(int k){ if(k==9){ print(); return; } for(int i=1;i<9;i++) if(f(k,i)){ set(k,i,1); dfs(k+1); set(k,i,0); } } bool f(int x,int y){ return !(vis[y+1]||vlr[x-y+8]||vrl[x+y-2]);//一个判断，列与对角线。 } void set(int x,int y,bool m){//m用来表示是标记还是回溯 if(m) a[x]=y; else a[x]=0; vis[y+1]=m; vlr[x-y+8]=m; vrl[x+y-2]=m; return; }提示
输出要列改成行，行改成列，这坑了我一把[狗头]不然
a[j]==i其实应该是a[i]==j。这题是真的坑。
倡议
倡议大家多写我这种优质题解。
像那些没有注释、说明的。要么为了刷RP，要么为了炫耀自己做出来了。AC名单已经可以展示了，就不要到题解装逼。还有，这样刷的RP有什么意义吗？
题解是为了教不会本题的人，不是为了像他么炫耀，让他们自惭的！
我题目做不出来的时候，看题解，什么都看不懂。到我做出来了才看得懂，那有什么意义！所以，我自本学期以来，一直写优质题解。但我也希望，自己，也可以从这种优质题解里学习，而不是看到一堆没有注释的烂题解后，愤愤回题面。
所以可以给我点个赞吗
-
1
C23huyating LV 7 @ 2024-1-24 11:40:45
#include<bits/stdc++.h> #define string xx break using namespace std; int q[8][8]={}; int x[100005]; int n=8; int cnt=0; bool place(int t){ for(int j=1;j<t;j++) if(x[t]==x[j]||t-j==abs(x[t]-x[j])) return false; return true; } long s=0; void f(int t){ if(t>n){ cnt++; cout<<"No. "<<cnt<<endl; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cout<<((x[j]==i)?1:0)<<' '; } cout<<endl; } return; } for(int i=1;i<=n;i++){ x[t]=i; if(place(t)) f(t+1); } } int main(){ system("color F1"); for(int a=0;a<8;a++){ q[0][a]=1;"xx"; for(int b=0;b<8;b++){ if(b!=a&&place(1)){ q[1][b]=1; for(int c=0;c<8;c++){ if(c!=b&&c!=a&&place(2)){ q[2][c]=1; for(int d=0;d<8;d++){ if(d!=c&&d!=b&&d!=a&&place(3)){ q[3][d]=1; for(int e=0;e<8;e++){ if(e!=d&&e!=c&&e!=b&&e!=a&&place(4)){ q[4][e]=1; for(int f=0;f<8;f++){ if(f!=e&&f!=d&&f!=c&&f!=b&&f!=a&&place(5)){ q[5][f]=1; for(int g=0;g<8;g++){ if(g!=f&&g!=e&&g!=d&&g!=c&&g!=b&&g!=a&&place(6)){ q[6][g]=1; for(int h=0;h<8;h++){ if(h!=g&&h!=f&&h!=e&&h!=d&&h!=c&&h!=b&&h!=a&&place(7)){ s++; q[7][h]=1; q[7][h]=0; } } q[6][g]=0; } } q[5][f]=0; } } q[4][e]=0; } } q[3][d]=0; } } } } q[1][b]=0; } } q[0][a]=0; }f(1); return 0; }C班不大，创造神话！
-
C23pengweixuan
@ 2024-1-24 11:41:34
其实就是把递归藏在了循环里面
-
其实就是把递归藏在了循环里面
-
C23panweiming
@ 2024-3-5 19:07:15
屎
-
-
0
C23lvzekai
LV 6
@ 2024-4-9 19:33:44
重做 更简洁
#include<bits/stdc++.h> using namespace std; const int n=8; int arr[1101][1101],ans; bool chack(int x,int y){ for(int i=0;i<n;i++) if(arr[i][y] || arr[x][i]) return 0; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i+j==x+y && arr[i][j]) return 0; if(i-j==x-y && arr[i][j]) return 0; } } return 1; } void ddd(int a){ if(a==8){ cout<<"No. "<<++ans<<endl; for(int i=0;i<n;i++){ for(int j=0;j<n;j++) cout<<arr[j][i]<<' '; cout<<'\n'; } } for(int i=0;i<n;i++){ if(chack(a,i)){ arr[a][i]=1; ddd(a+1); arr[a][i]=0; } } } int main(){ ddd(0); return 0; } -
-1
C24zhaozicheng LV 8 @ 2025-1-17 14:03:07
-
-1
C23panweiming
LV 8
@ 2024-3-6 13:30:54
#include<iostream> using namespace std; int a[11][45]; int ans=0; bool check(int x,int y) { for(int i=0;i<8;i++)//横 { if(a[x][i]) { return 0; } } for(int i=0;i<8;i++)//竖 { if(a[i][y]) { return 0; } } for(int i=0;i<8;i++)//对角线 { for(int j=0;j<8;j++) { if(a[i][j] && i-j==x-y) { return 0; } } } for(int i=0;i<8;i++)//对角线 { for(int j=0;j<8;j++) { if(a[i][j] && i+j==x+y) { return 0; } } } return 1; } void dfs(int x) { if(x==8)//最后的行时 { ans++; cout<<"No. "<<ans<<endl;//"No. "后面有空格,把我坑死了 for(int i=0;i<8;i++) { for(int j=0;j<8;j++) { cout<<a[j][i]<<" ";//注意 } cout<<endl; } return; } for(int i=0;i<8;i++) { if(check(x,i))//是否可以放 { a[x][i]=1;//标记 dfs(x+1);//递归 a[x][i]=0;//回溯,恢复操作 } } } int main() { dfs(0); return 0;//完结散花 } -
-3
C23liyanlan LV 4 @ 2024-1-26 10:12:42
easy~
#include <iostream> #include <cmath> using namespace std; int n; int x[100000]; int cnt; bool place(int t) { for(int j = 1; j < t; j++) { if(x[t] == x[j] || t - j == abs(x[t] - x[j])) return false; } return true; } void backtrack(int t) { if(t > n) { cnt++; cout << "No. " << cnt << endl; for(int j = 1; j<= n; j++) { for(int i = 1; i <= n; i++) cout << ((x[i] == j) ? 1 : 0) << " "; cout << endl; } return; } for(int i = 1; i<= n; i++) { x[t] = i; if(place(t)) backtrack(t+1); } } int main() { n = 8; cnt = 0; backtrack(1); return 0; }
C24zhengshunyuan
LV 6
@ 2025-1-16 20:10:34
- 1