n皇后问题合集.docx

package nqueen;import java.io.*;/** * * 程序目的：回溯法做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) {this.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(tN)表示搜索到了叶子节点，结束此次回溯,否则根据限界条件向下搜索。if (t N) {for (i = 1; i = N; i++) {for (int j = 1; j = N; j++) {if (position[i] == j) {System.out.print(Q );} else {System.out.print(- );}}System.out.println();}count++;System.out.println(========================);} 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 stubint n;Backtrack bt = new Backtrack();// 程序中数据的输入System.out.print(请输入问题的规模：);BufferedReader br = new BufferedReader(new InputStreamReader(System.in));n = Integer.parseInt(br.readLine());bt.setN(n);long start = System.currentTimeMillis();// 获得程序开始执行时的时间bt.Back(1);long end = System.currentTimeMillis();// 获得程序结束时的时间System.out.println(Time: + (end - start));System.out.println(bt.getN() + -皇后问题的解法共有： + bt.getCount() + 种);}}@@@@@@@@@@@@@@@@@@//回溯法之N皇后问题当N10，就有点抽了~~/*结果前total行每行均为一种放法，表示第i行摆放皇后的列位置，第total+1行，输出total*/ #includestdio.h#includestdlib.h int n,stack[100]; //存当前路径int total; //路径数void make(int l) //递归搜索以stack[l]为初结点的所有路径{ int i,j; //子结点个数 if (l==n+1) { total=total+1; //路径数+1 for(i=1;i=n;i++)