n皇后问题：n*n棋盘:使其不能相互攻击：即任意两个皇后不可在同一行，同一列，或同一条对角线上；
使用回溯法；
回溯法思想：一个解空间(X0,X2...Xn-1)，显式约束条件，隐式约束条件Xi之间的关系；
void rcallback(int k){
for( 满足下式的每个X(k):
满足显式约束条件即 X属于T(x1,X2,X3...Xk-1) 并且满足隐式约束条件：B(X1,X2...XK)=true)
if( (X0,X2...Xn-1)是一条已抵达答案结点的路径） 打印；
rcallback(k+1);
}
}
package com.algothrim;
/*
*
* 不失一般性：设第i行放置了第i个皇后；解空间X={X0,X1,X2...Xn-1};其中Xi表示第i个皇后放在第Xi列上。
* 两个皇后(i,Xi),(j,Xj) :在同一列情况仅当： Xi=Xj; 在同一对角线情况仅当：|Xj-Xi|=|j-i|;
*
* 初始化第0个皇后在-1列； 行标line=0;
* 使第line个皇后移到下一列，判断是否可放：若不可以，则继续移到下一列；
*
* 若第line个皇后移到了第n列，即表示无解，line=line-1回溯。
* 否则：判断line=n-1即最后一个皇后，那么打印输出这条路径。
* 若不是最后一个皇后，line=line+1;移到下一行，放置下一个皇后。
*/
public class NQueens{
public boolean place(int[] X,int k){
for(int i=0;i<k;i++){
if(X[i]==X[k] || abs(X[i],X[k])==abs(k,i))
return false;
}
return true;
}
public int abs(int a,int b){
return a>b ? a-b : b-a;
}
public void nQueens(int n){
int[] X=new int[n];
int line=0;
X[0]=-1;
while(line>-1){
X[line]=X[line]+1; ///移到下一列
while(X[line]<n && !place(X,line)) //此处能放置这个皇后吗？
X[line]=X[line]+1;
if(X[line]<n){
if(line==n-1) print(X);
else{
line=line+1; //转向下一行
X[line]=-1;
}
}else{
line=line-1; //回溯
}
}
}
public void print(int[] X){
System.out.println("一种解方案:");
for(int i=0;i<X.length;i++)
System.out.print(" "+X[i]);
System.out.println();
}
public static void main(String[] args) {
NQueens nQueens=new NQueens();
nQueens.nQueens(8);
}
}