n皇后问题 (回溯法) 原创

1、方法思想回溯法是一个既带有系统性又带有跳跃性的搜索算法。

它在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。

算法搜索至解空间树的任何一结点时，先判断该结点是否包含问题的解。

如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则进入该子树，继续按深度优先策略搜索。

代码实现：class Queen{friend int nQueen(int)private:bool Place(int k);void Backtrack(int t);int n, //皇后个数*n; //当前解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++; //达到叶结点elsefor (int i=1;i<=n;i++) { //搜索子结点x[t]=i; //进入第i个子结点if (Place(t)) Backtrack(t+1);}}int nQueen(int n){Queen X;//初始化XX.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; return X.sum; }。

N皇后问题及答案解题⽬在⼀张N∗N的国际象棋棋盘上，放置N个皇后，使得所有皇后都⽆法互相直接攻击得到，（皇后可以直接攻击到她所在的横⾏，竖列，斜⽅向上的棋⼦），现在输⼊⼀个整数N，表⽰在N∗N的棋盘上放N个皇后，请输出共有多少种使得所有皇后都⽆法互相直接攻击得到的⽅案数。

例如下⾯这样的摆法，是4皇后的⼀个解 （1代表有皇后，0代表没有）0 1 0 00 0 0 11 0 0 00 0 1 0输⼊⼀个整数N，代表皇后的个数输出输出⽅案数样例输⼊样例输⼊14样例输⼊28样例输出样例输出12样例输出292⼀、DFS+回溯(1)设已经放好的皇后坐标为(i,j),待放⼊的皇后坐标为(r,c)，则它们满⾜以下关系：（1）不同⾏，即 i ≠ r；（2）不同列，即 j ≠ c；（3）不在斜对⾓线上，即 |i-r| ≠ |j-c|.可以在⼀⾏逐列尝试，这样就不⽤考虑（1）了。

#include <iostream>#include <algorithm>#include <cstring>using namespace std;int n, tot = 0;int col[15] = {0}, ans[15] = {0}; //col[i]的值为第i⾏的皇后的列数的值，即j,ans[]数组⽤来存放结果bool check(int c, int r) //检查是否和已经放好的皇后冲突{for (int i = 0; i < r; i++)if (col[i] == c || (abs(col[i] - c) == abs(i - r))) //因为是逐⾏放置，所以只考虑纵向和斜向return false;return true;}void dfs(int r,int m) //在第r⾏放皇后,m表⽰⾏数{if(r==m){ //r==m,即皇后放到最后⼀⾏，满⾜条件，tot++,返回;tot++;return;}for(int c=0;c<m;c++) //在此⾏逐列尝试if(check(c,r)){ //检查是否冲突col[r]=c; //不冲突就在此列放皇后dfs(r+1,m); //转到下⼀⾏继续尝试}}int main(){cin>>n;for (int i = 0; i <= 13; i++) //算出所有N皇后的答案，先打表，不然会超时{memset(col, 0, sizeof(col)); //清空col，准备计算下⼀个N皇后问题tot = 0;dfs(0,i);ans[i] = tot;}cout << ans[n] << endl;return 0;}在上述程序中，dfs()⼀⾏⾏放置皇后，时间复杂度为O(N!)；check()判断冲突，时间复杂度为O(N)，总的为O(N*N!)！⾮常的⾼。

Tree-回溯法求N皇后问题#include <stdio.h>#include <malloc.h>#define N 4 //N皇后typedef int Chessboard[N + 1][N + 1]; //第0号位置不用bool check(Chessboard cb, int i, int j) { //看棋盘cb是否满足合法布局int h, k;int m = i + j, n = i - j;for(h=1; h<i; h++) {if(cb[h][j] == 1 && h != i) return false; //检查第j列if(m-h<=N && cb[h][m-h] == 1 && h != i) return false; //检查斜的，m-h<=N是为了保证不越界if(h-n<=N && cb[h][h-n] == 1 && h != i) return false; //检查斜的，h-n<=N是为了保证不越界}for(k=1; k<N; k++)/*检查第i行的*/ if(cb[i][k] == 1 && k != j) return false;return true;}void printfChessboard(Chessboard cb) {//打印棋盘int i, j;for(i=1; i<=N; i++) {for(j=1; j<=N; j++) printf("%d ", cb[i][j]);printf("\n");}printf("\n");}/*进入本函数时，在n*n棋盘前n-1行已放置了互不攻击的i-1个棋子。

现从第i行起继续为后续棋子选择合适位置。