N皇后问题Java回溯法实现.doc

public class Queens {
int N;
int X[];
static long count = 0;
public Queens(int N){
this.N = N;
X = new int[N+1];
}
public boolean Place(int k){
int i = 1;
while(i<k){
if((X[i]==X[k])||(Math.abs(X[i]-X[k])==Math.abs(i-k))) //同一列或对角线
return false;
i++;
}
return true;
}
public void Print(){
count++;
for(int i=1;i<N+1;i++)
System.out.print(X[i]+"\t");
System.out.println();
}
public void Position(){
int k = 1; //当前行
X[1] = 0; //当前列
while(k>0){
X[k] = X[k]+1; //移到下一列
while(X[k]<=N&&!Place(k)){
X[k] = X[k]+1;
}
//System.out.print(k+":"+X[k]+" ");
if(X[k]<=N){ //找到一个位置
if(k==N){
Print();k--; //回溯到上一层，查找下一个
}else{
k++;X[k]=0; //转到下一行
}
}else{
k = k-1; //回溯到上一层
}
}
}
public static void main(String[] args) {
Queens queens = new Queens(16); //修改此处的数字可求任意皇后问题
long begintime = System.currentTimeMillis();
queens.Position();
System.out.println("\r\nOK,共有 "+count+" 种解法！");
long endtime = System.currentTimeMillis();
System.out.println("耗时 "+(endtime-begintime)/1000+" 秒");
}
}