n皇后问题合集

《n皇后问题合集》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、packagenqueen;importjava.io.*;/****程序目的：回溯法做N皇后问题**@authorSun**2011-11-20*/publicclassBacktrack{/***@paramargs*/privateintN=65535;//问题的规模(注意：此处必须要定义一个数值，因为在下一句数组的定义时要用到此数字，否则报错)privateint[]position=newint[N+1];//存放解存放的位置privateintcount=0;//存放解的个数/***设置问题的规模*/publicvoidsetN(intn){this.N=n;}/***返回

2、规模值*@return*/publicintgetN(){returnN;}/***得到解的个数**@return*/publicintgetCount(){returncount;}/***此位置能否放置皇后**@paramrow*@return*/publicbooleanSafe(introw){inti;for(i=1;i

3、

4、i-position[i]==row-position[row]

5、

6、i+position[i]==row+position[row]){returnfalse;}}returnt

7、rue;}/***回溯函数，搜索解空间**@paramt*/publicvoidBack(intt){inti;//t表示搜索解空间树当前的深度。N代表解空间树的深度。//if(t>N)表示搜索到了叶子节点，结束此次回溯,否则根据限界条件向下搜索。if(t>N){for(i=1;i<=N;i++){for(intj=1;j<=N;j++){if(position[i]==j){System.out.print("Q");}else{System.out.print("-");}}System.out.println();}count++;System.out.println("====

8、====================");}else{for(i=1;i<=N;i++){position[t]=i;if(Safe(t)){Back(t+1);}}}}publicstaticvoidmain(String[]args)throwsIOException{//TODOAuto-generatedmethodstubintn;Backtrackbt=newBacktrack();//程序中数据的输入System.out.print("请输入问题的规模：");BufferedReaderbr=newBufferedReader(newInputStreamReader

9、(System.in));n=Integer.parseInt(br.readLine());bt.setN(n);longstart=System.currentTimeMillis();//获得程序开始执行时的时间bt.Back(1);longend=System.currentTimeMillis();//获得程序结束时的时间System.out.println("Time:"+(end-start));System.out.println(bt.getN()+"-皇后问题的解法共有："+bt.getCount()+"种");}}@@@@@@@@@@@@@@@@@@//回溯法之N

10、皇后问题当N>10，就有点抽了~~/*结果前total行每行均为一种放法，表示第i行摆放皇后的列位置，第total+1行，输出total*/#include#includeintn,stack[100];//存当前路径inttotal;//路径数voidmake(intl)//递归搜索以stack[l]为初结点的所有路径{inti,j;//子结点个数if(l==n+1){total=total+1;//路径数+1for(i=1;i<=n;i++)printf("%-3d",stack[i]);//输出第i行皇后的列位置stack[i]printf(

11、"");exit;//回溯（若试题仅要求一条路径，则exit改为halt即可）}for(i=1;i<=n;i++){stack[l]=i;//算符i作用于生成stack[l-1]产生子状态stack[l];if(!att(l,i))make(l+1);}//再无算符可用，回溯}intatt(intl,inti){intk;for(k=1;k

12、

13、i==stack[k])re