题目描述
请设计一种算法，解决著名的n皇后问题。这里的n皇后问题指在一个nxn的棋盘上放置n个棋子，使得每行每列和每条对角线上都只有一个棋子，求其摆放的方法数。
给定一个int n，请返回方法数，保证n小于等于15
测试样例：1
返回：1
思路：
【全文】
回溯法是一种通用的搜索算法，几乎可以用于求解任何可计算的问题。算法的执行过程就像是在迷宫中搜索一条通往出口的路线，总是沿着某一方向向前试探，若能走通，则继续向前进；如果走不通，则要做上标记，换一个方向再继续试探，直到得出问题的解，或者所有的可能都试探过为止。
下面，用经典的8皇后问题为例来讲解如何使用回溯的思想解决问题。
8皇后问题是：在8×8的棋盘上摆放8个皇后，使其不能互相攻击，即任意的两个皇后不能处在同一行，同一列，或同一斜线上。可以把八皇后问题拓展为n皇后问题，即在n×n的棋盘上摆放n个皇后，使其任意两个皇后都不能处于同一行、同一列或同一斜线上。
首先需要对棋盘进行描述。直观地，棋盘可以用二维数组表示，有皇后的棋格对应数组元素值为1，无皇后的棋格对应数组元素值为0。但这种存储结构并不是最简单有效的选择。
图8.21中左边部分给棋盘的行、列编了号，提供的摆放方法，就是问题的一个解。右边的部分，将各行上皇后所在的列数记录下来，用这8个数字（4, 6, 8, 2, 7, 1, 3, 5），也构成了对问题解的一种描述。 
图8.21 8皇后问题的一个解
由此可以看出，可以定义一个一维数组int x[N];，用x[i]的值表示第i行上皇后所在的列数，n皇后问题的解可以用（x[1], x[2], ….. x[n]）的形式描述。
解决了数据表示的问题，设计数据处理的方法。这里要用回溯的策略，设计计算机对n皇后问题的求解方法。以4皇后为例，如图8.22所示，在图8.22(a)中，第1行第1列上放置一个皇后，图8.22(b)中确定第2行的可能放法，在尝试第1列、第2列由于相互攻击而放弃之后，确定在第3列放置可以继续，在图8.22(c)中继续对第3行进行考察，发现将所有4列都尝试过了，也没有办法将皇后安排一个合适的位置，对第4行做任何的尝试都没有意义，这时产生回溯，结果是在图8.22(d)中将第2行的皇后安排到第4列，然后第3行的暂时可以放在第2列，在图8.22(e)中试着确定第4行的皇后，却发现无解再次回溯，只能够如图8.22(f)所示将第1行的皇后放到第2列，再经图8.22(g)、(f)之后找到4皇后问题的一个解，那就是图8.22(g)的（2, 4, 1, 3）。 
图8.22 用回溯找出4皇后问题一个解的过程
在图8.23中，给出了求出4皇后问题所有解的完整过程的描述。图中（1 * * *)对应图8.22(a)中第1行皇后安排在第1列，其他行待定的状态，接下来的（1 3 * *）对应了图8.22(b)中第2行皇后安排在第3列的状态。可以判断出在这个状态下，继续尝试并不能够完成求解，于是发生回溯（其下方的B代表回溯），于是下一个尝试的状态将是（1 4 * *），……。将这样的过程继续下去，能够找出4皇后问题的所有解（2 4 1 3）和（3 1 4 2），如图8.23中两个加网格背景的结点。 
图8.23 求出4皇后问题所有解的完整过程
搞清楚用回溯法求解的过程后，将关注如何基于（x[1], x[2], ….. x[n]）形式的解结构，写出让计算机完成求解过程的代码。4皇后问题尚且可以在纸上画出解，8皇后问题的可能解有8!=40320种，最终解有92种，必须要依靠计算机求解了。
什么样的解才是可行的？需要描述出任何两个皇后可以“互相攻击”这样的条件：
（1）有两个皇后处在同一行：解的结构（x[1], x[2], ….. x[n]）已经保证同一行不会出现两个皇后。
（2）有两个皇后处在同一列：表示为x[i]=x[k]，假如在图8.23中出现表示为（1 1 * *）、（4 2 3 2）之类的结点，则说明有两个皇后在同一列了。
（3）有两个皇后处在同一斜线：若两个皇后的摆放位置分别是第i行第x[i]列、第k行第x[k]列，若他们在棋盘上斜率为-1的斜线上，满足条件i-x[i]=k-x[k]，例如（1 4 3 *）、（4 1 2 *）；若他们在棋盘上斜率为1的斜线上，满足条件i+x[i]=k+x[k]。将这两个式子分别变换成i-k=x[i]-x[k]和i-k=x[k]-x[i]，例如（3 4 1 *）。综合两种情况，两个皇后位于同一斜线上表示为|i-k|=|x[i]-x[k]|。
在下面的程序实现中，place(x, k)函数用于判断在第k行第x[k]列放置皇后，是否会与前面摆放好的皇后产生相互攻击。只要有某行（第i行）的皇后与这个第k行的皇后处在同一列（x[i]=x[k]）或者处在同一斜线（|i-k|=|x[i]-x[k]|），则立即返回假(0)，表示不可能构成解。
再接下来，就是在实现问题求解的nQueens(x, n)函数中，从第1行开始，逐行逐列地考察皇后的摆放，当遇到某一行所有可能情况试过不必再深入到下一行考察时，及时回溯到上一行，接着考察。
程序实现中，将保存解的数组定义成了动态数组。多分配一个单元，因为数组的首元素x[0]一直空闲未用，有用的单元是x[1]到x[n]。
注解：定义为15行，因为题目不会超过15行，每次将这个皇后放进去，然后判定刚才放的是满足条件的么，如果是继续放，如果不满足直接return。到第8个皇后都放好，结果就+1.
import java.util.*;
public class Queens {
int sum=0;
int col[]=new int[15];
public int nQueens(int n) {
// write code here
Search(0,n);
return sum;
}
public void Search(int cur,int n ){
for(int i =0;i<n;i++){
col[cur]=i;
if(Place(cur)){
if(cur==n-1){sum++;return;}
else {
Search(cur+1, n);
}
}
}
}
public boolean Place(int cur){
for (int i = 0; i < cur; i++) {
if(col[i]==col[cur]||Math.abs(col[i]-col[cur])==(cur-i)){
return false;
}
}
return true;
}
}