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(irn true;
}
public void Print(){
count++;
for(int i=1;i0){
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+" 秒");
}
}