n皇后问题合集.docx

package nqueen;
import .*;
/**
*
* 程序目的:回溯法做N皇后问题
*
* ***@author Sun
*
* 2011-11-20
*/
public class Backtrack {
/**
* ***@param args
*/
private int N = 65535;// 问题的规模(注意:此处必须要定义一个数值,因为在下一句数组的定义时要用到此数字,否则报错)
private int[] position = new int[N + 1];// 存放解存放的位置
private int count = 0;// 存放解的个数
/**
* 设置问题的规模
*/
public void setN(int n) {
= n;
}
/**
* 返回规模值
* ***@return
*/
public int getN() {
return N;
}

/**
* 得到解的个数
*
* ***@return
*/
public int getCount() {
return count;
}
/**
* 此位置能否放置皇后
*
* ***@param row
* ***@return
*/
public boolean Safe(int row) {
int i;
for (i = 1; i < row; i++) {
if (position[row] == position[i]
|| i - position[i] == row - position[row]
|| i + position[i] == row + position[row]) {
return false;
}
}
return true;
}
/**
* 回溯函数,搜索解空间
*
* ***@param t
*/
public void Back(int t) {
int i;
// t表示搜索解空间树当前的深度。N代表解空间树的深度。
// if(t>N)表示搜索到了叶子节点,结束此次回溯,否则根据限界条件向下搜索。
if (t > N) {
for (i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (position[i] == j) {
("Q ");
} else {
("- ");
}
}
();
}
count++;
("========================");
} else {
for (i = 1; i <= N; i++) {
position[t] = i;
if (Safe(t)) {
Back(t + 1);
}
}
}
}
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
int n;
Backtrack bt = new Backtrack();
// 程序中数据的输入
("请输入问题的规模:");
BufferedReader br = new BufferedReader(new InputStreamReader());
n = (());
(n);
long start = ();// 获得程序开始执行时的时间
(1);
long end = ();// 获得程序结束时的时间
("Time:" + (end - start));
(() + "-皇后问题的解法共有:" + () + "种");
}
}
@@@@@@@@@@@@@@@@@@
//回溯法之N皇后问题当N>10,就有点抽了~~
/*结果前to