问题描述：
在n*n的棋盘上放置彼此不受攻击的n个皇后。按国际象棋的规则，皇后可以与之处在同一行或者同一列或同一斜线上的棋子。
n后问题等价于在n*n格的棋盘上放置n皇后，任何2个皇后不放在同一行或同一列的斜线上。
算法设计：
|i-k|=|j-l|成立，就说明2个皇后在同一条斜线上。可以设计一个place函数，测试是否满足这个条件。
1 当i>n时，算法搜索至叶节点，得到一个新的n皇后互不攻击放置方案，当前已找到的可行方案sum加1.
2 当i<=n时，当前扩展结点Z是解空间中的内部结点。该结点有x[i]=1,2,3....n共n个儿子节点。
对当前扩展结点Z的每个儿子节点，由place检察其可行性。并以深度优先的方式递归地对可行子树，或剪去不可行子树。
算法描述：
#include <iostream> #include <cstdlib> using namespace std; class Queen{ friend int nQueen(int); private: bool Place(int k); void Backtrack(int t); int n, * x; long sum; }; bool Queen::Place(int k) { for(int j=1;j<k;j++) if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false; return true; } void Queen::Backtrack(int t) { if(t>n) sum++; else for(int i=1;i<=n;i++) { x[t] = i; if(Place(t)) Backtrack(t+1); } } int nQueen(int n) { Queen X; X.n = n; X.sum = 0; int *p = new int [n+1]; for(int i=0;i<=n;i++) p[i] = 0; X.x = p; X.Backtrack(1); delete [] p; cout<<X.sum<<endl; return X.sum; } int main() { nQueen(4); nQueen(2); nQueen(3); return 0; }
执行结果：
迭代回溯：
数组x记录了解空间树中从根到当前扩展结点的路径，这些信息已包含了回溯法在回溯时所需要的信息。利用数组x所含的信息，可将上述回溯法表示成非递归形式，进一步省去O(n)递归栈空间。
n后问题的非递归迭代回溯法Backtrack可描述如下：
#include <iostream> #include <cstdlib> using namespace std; class Queen{ friend int nQueen(int); private: bool Place(int k); void Backtrack(void);//......... int n, * x; long sum; }; bool Queen::Place(int k) { for(int j=1;j<k;j++) if( ( abs(k-j) == abs(x[j]-x[k]) ) ||( x[j] == x[k] ) ) return false; return true; } void Queen::Backtrack(void)//...... { x[1] = 0; int k = 1; while(k>0) { x[k]+=1; while( (x[k]<=n) && !(Place(k)) )//k还不是最后的叶子结点，且位置没有冲突 x[k] += 1; if(x[k] <= n) if(k == n)//k是叶子结点 sum++; else { k++; x[k] = 0; } else k--; } } int nQueen(int n) { Queen X; X.n = n; X.sum = 0; int *p = new int [n+1]; for(int i=0;i<=n;i++) p[i] = 0; X.x = p; X.Backtrack();//...... delete [] p; cout<<X.sum<<endl; return X.sum; } int main() { nQueen(4); nQueen(2); nQueen(3); return 0; }
执行结果：
本文转自博客园xingoo的博客，原文链接：n后问题-回溯法，如需转载请自行联系原博主。
