?? nqueen.java
字號:
/**
* 利用回溯法求解N皇后問題
* 2008/12/04
* @author jok
* @version 1.0
*
*/
package cn.com.csu.algorithm;
public class NQueen {
private int n;//皇后的個數
private int[] x;//x[i]表示第i個皇后在第i列第x[i]行
private long sum;//所有的可行解的個數
public long nQueen(int n) {
this.n=n;
sum=0;
x= new int[n+1];
for(int i=0;i<=n;i++) {
x[i] =0;
}
backtrack();
return sum;
}
private void backtrack() {
int k=1;
while(k>0) {
x[k]+=1;//每次下移一行
while((x[k]<=n) && !(place(k))) {
x[k]+=1;//若第x[k]行不能放則判斷下一行
}
if(x[k]<=n) {
if(k==n) {
sum++;//k==n說明所有的皇后都已經排列好,可行解數目加一
for(int i=1;i<x.length;i++) {
System.out.println("第"+i+"個皇后在第"+x[i]+"行第"+i+"列");
}
System.out.println("---------------------");
}
else {
k++;//若不是第n列,則繼續判斷下一列
x[k]=0;
}
}
else {
k--;//x[k]>n則說明第k列無法排進去,則回溯
}
}
}
/*
* 判斷第k列第x[k]行能否放皇后,返回true則說明能
*/
private boolean place(int k) {
for(int j=1;j<k;j++) {
if((Math.abs(k-j) == Math.abs(x[j]-x[k])) || (x[j] == x[k])) {
return false;
}
}
return true;
}
public static void main(String[] args) {
NQueen nq = new NQueen();
int n = 4;
nq.nQueen(n);
System.out.println(n+"皇后問題的可行解有"+nq.sum+"個");
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -