1213：八皇后问题
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。
【输入】
(无)
【输出】
按给定顺序和格式输出所有八皇后问题的解（见样例）。
【输入样例】
（无）
【输出样例】
No. 1
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
No. 2
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0
...以下省略
【来源】
No
1. #include<iostream> 2. #include<cstdio> 3. #include<iomanip> 4. using namespace std; 5. int a[9],b[9],c[17],d[17]; 6. int sum=0; 7. void print() 8. { 9. sum++; 10. cout<<"No. "<<sum<<endl; 11. for(int i=1;i<=8;i++){ 12. for(int j=1;j<=8;j++) 13. if(i==a[j]) cout<<"1 "; 14. else cout<<"0 "; 15. cout<<endl; 16. } 17. } 18. int dfs(int i) 19. { 20. 21. for(int j=1;j<=8;j++){ 22. if((b[j]==0)&&(c[i+j]==0)&&(d[i-j+7]==0)){ 23. a[i]=j; 24. b[j]=1; 25. c[i+j]=1; 26. d[i-j+7]=1; 27. if(i==8) print(); 28. else dfs(i+1); 29. b[j]=0; 30. c[i+j]=0; 31. d[i-j+7]=0; 32. } 33. } 34. } 35. int main() 36. { 37. dfs(1); 38. return 0; 39. }
