N皇后问题Java回溯法实现

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

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

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) {

相关推荐
相关主题
热门推荐