n皇后問題合集

《n皇后問題合集》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、packagenqueen;importjava.io.*;/****程序目的：回溯法做N皇后問題**@authorSun**2011-11-20*/publicclassBacktrack{/***@paramargs*/privateintN=65535;//問題的規(guī)模(注意：此處必須要定義一個數(shù)值，因?yàn)樵谙乱痪鋽?shù)組的定義時要用到此數(shù)字，否則報(bào)錯)privateint[]position=newint[N+1];//存放解存放的位置privateintcount=0;//存放解的個數(shù)/***設(shè)置問題的規(guī)模*/publicvoidsetN(intn){this.N=n;}/***返回

2、規(guī)模值*@return*/publicintgetN(){returnN;}/***得到解的個數(shù)**@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;}/***回溯函數(shù)，搜索解空間**@paramt*/publicvoidBack(intt){inti;//t表示搜索解空間樹當(dāng)前的深度。N代表解空間樹的深度。//if(t>N)表示搜索到了葉子節(jié)點(diǎn)，結(jié)束此次回溯,否則根據(jù)限界條件向下搜索。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();//程序中數(shù)據(jù)的輸入System.out.print("請輸入問題的規(guī)模：");BufferedReaderbr=newBufferedReader(newInputStreamReader

9、(System.in));n=Integer.parseInt(br.readLine());bt.setN(n);longstart=System.currentTimeMillis();//獲得程序開始執(zhí)行時的時間bt.Back(1);longend=System.currentTimeMillis();//獲得程序結(jié)束時的時間System.out.println("Time:"+(end-start));System.out.println(bt.getN()+"-皇后問題的解法共有："+bt.getCount()+"種");}}@@@@@@@@@@@@@@@@@@//回溯法之N

10、皇后問題當(dāng)N>10，就有點(diǎn)抽了~~/*結(jié)果前total行每行均為一種放法，表示第i行擺放皇后的列位置，第total+1行，輸出total*/#include#includeintn,stack[100];//存當(dāng)前路徑inttotal;//路徑數(shù)voidmake(intl)//遞歸搜索以stack[l]為初結(jié)點(diǎn)的所有路徑{inti,j;//子結(jié)點(diǎn)個數(shù)if(l==n+1){total=total+1;//路徑數(shù)+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]產(chǎn)生子狀態(tài)stack[l];if(!att(l,i))make(l+1);}//再無算符可用，回溯}intatt(intl,inti){intk;for(k=1;k

12、

13、i==stack[k])re