问题 D: 【递归入门】n皇后 问题（原始的8皇后问题） 时间限制: 1 Sec 内存限制: 128 MB 献花: 40 解决: 28 [献花][花圈][TK题库] 题目描述 会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
输入 一个整数n（ 1 < = n < = 10 ) 输出 每行输出对应一种方案，按字典序输出所有方案。每种方案顺序输出皇后所在的列号，相邻两数之间用空格隔开。如果一组可行方案都没有，输出“no solute!” 样例输入 4 样例输出 2 4 1 3 3 1 4 2
#include <iostream> #include <cmath> using namespace std; const int MaxN = 25; int c = 0 ,Data[MaxN] = {0}; bool hashTable[MaxN] = {0}; void DFS(int n,int k) { if(k > n) { for(int i=1;i<=n;++i) { cout << Data[i]; if(i != n) cout << " "; } cout << endl; ++c; } for(int i = 1;i<=n;++i) { if(hashTable[i] == false) { bool isvalid = true; for(int m = 1;m < k;++m) { if(k-m == abs(i-Data[m])) { isvalid = false; break; } } if(isvalid) { hashTable[i] = true; Data[k] = i; DFS(n,k+1); hashTable[i] = false; } } } } int main() { #ifdef _Debug freopen("data.txt","r+",stdin); #endif // _Debug int n; while(cin >> n) { c=0; DFS(n,1); if(c == 0) cout << "no solute!"<<endl; } return 0; } /************************************************************** Problem: 5976 User: Sharwen Language: C++ Result: 升仙 Time:4 ms Memory:1704 kb ****************************************************************/