Java 八皇后問題解釋

public class Queen{//同欄是否有皇后，1表示有private int[] column;//右上至左下是否有皇后private int[] rup;//左上至右下是否有皇后private int[] lup;//解答private int[] queen;//解答編號private int num;public Queen(){column=new int[8+1];rup=new int[(2*8)+1];lup=new int[(2*8)+1];for(int i=1;i=8;i++)column[i]=0;for(int i=1;i=(2*8);i++)rup[i]=lup[i]=0; //初始定義全部無皇后 queen=new int[8+1];} public void backtrack(int i){if(i8){showAnswer();}else{for(int j=1;j=8;j++){if((column[j]==0)(rup[i+j]==0)(lup[i-j+8]==0)){//若無皇后queen[i]=j;//設定為占用column[j]=rup[i+j]=lup[i-j+8]=1;backtrack(i+1); //循環調用column[j]=rup[i+j]=lup[i-j+8]=0;}}}} protected void showAnswer(){num++;System.out.println("\n解答"+num); for(int y=1;y=8;y++){for(int x=1;x=8;x++){if(queen[y]==x){System.out.print("Q");}else{System.out.print(".");}} System.out.println();}} public static void main(String[]args){Queen queen=new Queen();queen.backtrack(1);}}

創新互聯主營山海關網站建設的網絡公司,主營網站建設方案,成都app軟件開發,山海關h5小程序設計搭建,山海關網站營銷推廣歡迎山海關等地區企業咨詢

八皇后問題的java代碼。

boolean[] diagonal = new boolean[16]; // 對角線安全標志

boolean[] undiagonal = new boolean[16]; // 反對角線安全標志

用上兩個判斷是否能放置棋子

在 n 行 n 列的國際象棋棋盤上，最多可布n個皇后。

若兩個皇后位于同一行、同一列、同一對角線上，

則稱為它們為互相攻擊。

n皇后問題是指找到這 n 個皇后的互不攻擊的布局。

n 行 n 列的棋盤上，主次對角線各有2n-1條。

利用行號i和列號j計算

主對角線編號k的方法是k = n+i-j-1；

計算次對角線編號k的方法是k = i+j

你主要是算法有些模糊罷了，現在我怕我說的不好將你弄的越來越混亂所以給你個叫形象的若是還不明白，call me

package 百度;

//演示程序：n個皇后問題

import java.io.*;

/*

在 n 行 n 列的國際象棋棋盤上，最多可布n個皇后。

若兩個皇后位于同一行、同一列、同一對角線上，

則稱為它們為互相攻擊。

n皇后問題是指找到這 n 個皇后的互不攻擊的布局。

n 行 n 列的棋盤上，主次對角線各有2n-1條。

利用行號i和列號j計算

主對角線編號k的方法是k = n+i-j-1；

計算次對角線編號k的方法是k = i+j

*/

//"n個皇后問題"之類定義

public class cQueen {

int n; //皇后問題的大小

int col[]; //數組，各列上有無皇后(0，1)

int md[]; //數組，各主對角線有無皇后(0，1)

int sd[]; //數組，各次對角線有無皇后(0，1)

int q[]; //數組，第i行上皇后在第幾列(0,n-1)

int Q; //已布皇后數，計數

int r; //n皇后問題的解的組數

//構造函數 n皇后問題的初始化

public cQueen(int m) {

n=m;Q=0;r=0;

col=new int[n];

md=new int[2*n-1]; //初始化0

sd=new int[2*n-1];

q=new int[n];

}

//函數：打印棋盤

public void showBoard() {

int i,j;

for(i=0;in;i++) {

for(j=0;jn;j++)

if(q[i]==j) System.out.print("1 ");

else System.out.print("0 ");

System.out.println();

}

r++; //解的組數

System.out.println("---------------");

}

//求解n皇后問題

/*

此函數試圖在n*n的棋盤的第i行上放一個皇后,

若找到可以放的位置,就遞歸調用自身試圖在i+1行

放另一個皇后,若第i行是最后一行，則打印棋盤。

*/

public void resolve(int i) {

int j;

// 在第i行給定后檢查棋盤上的每一列

for(j=0;jn;j++) {

//如果在第i行的第j列可以布放皇后

if(col[j]==0md[n+i-j-1]==0sd[i+j]==0){

Q++;q[i]=j; //布放皇后，第i行皇后在第幾列

// 標記新布皇后的攻擊范圍

col[j]=md[n+i-j-1]=sd[i+j]=1;

// 如果已經布了n個皇后（得到了一組解）,

// 把棋盤（解）打印出來。

if(Q==n) showBoard();

// 否則，遞歸。在第i行第j列布放皇后的前提下，

//試探下一行(i+1行)在哪一列布皇后？

else if(in-1) resolve(i+1);

else resolve(0); //因為約定起始行可以任選

//移除在第i行的第j列新布的皇后，

//并消除所標記的攻擊范圍，為回溯作準備。

Q--; q[i]=0;

col[j]=md[n+i-j-1]=sd[i+j]=0;

//試探在第i行的第j+1列新布皇后的方案（新解）

}

} //下一列，j循環

//對于給定的行,列掃描完畢后，從這里回溯。

}

//輸出解的個數

public void HowMany() {

System.out.println(n+"皇后問題共有解"+r+"組。");

}

//主方法main()

public static void main(String []args) {

//定義一個8皇后問題（有92組解）

cQueen Q1=new cQueen(8); //大于10，你的微機可能要死機！

//第一個皇后可以在任意一行布放

Q1.resolve(0); //參數在0到n-1之間任選

Q1.HowMany();

}

} //類Queen定義結束

關于看代碼的人人都知道的小技巧，最小試探法來輸出結果進行比較和分析

N皇后問題10秒內能算出的最大個數，請問什么代碼能實現呢，這個最大的個數是多少，代碼又是什么

package?com.newflypig.eightqueen;

import?java.util.Date;

/**

*?在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，

*?即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。

*?下面使用遞歸方法解決

*?@author?newflydd@189.cn

*

*/

public?class?EightQueen?{

private?static?final?short?N=15; //使用常量來定義，方便之后解N皇后問題

private?static?int?count=0; //結果計數器

private?static?int?K=0;

public?static?void?main(String[]?args)?{

for(K=9;K=N;K++){

count=0;

Date?begin?=new?Date();

//初始化棋盤，全部置0

short?chess[][]=new?short[K][K];

for(int?i=0;iK;i++){

for(int?j=0;jK;j++){

chess[i][j]=0;

}

}

putQueenAtRow(chess,0);

Date?end?=new?Date();

System.out.println("解決?"?+K+?"?皇后問題，用時："?+String.valueOf(end.getTime()-begin.getTime())+?"毫秒，計算結果："+count);

}

}

private?static?void?putQueenAtRow(short[][]?chess,?int?row)?{

/**

?*?遞歸終止判斷：如果row==N，則說明已經成功擺放了8個皇后

?*?輸出結果，終止遞歸

?*/

if(row==K){

count++;

// System.out.println("第?"+?count?+"?種解：");

// for(int?i=0;iN;i++){

// for(int?j=0;jN;j++){

// System.out.print(chess[i][j]+"?");

// }

// System.out.println();

// }

return;

}

short[][]?chessTemp=chess.clone();

/**

?*?向這一行的每一個位置嘗試排放皇后

?*?然后檢測狀態，如果安全則繼續執行遞歸函數擺放下一行皇后

?*/

for(int?i=0;iK;i++){

//擺放這一行的皇后，之前要清掉所有這一行擺放的記錄，防止污染棋盤

for(int?j=0;jK;j++)

chessTemp[row][j]=0;

chessTemp[row][i]=1;

if(?isSafety(?chessTemp,row,i?)?){

putQueenAtRow(chessTemp,row+1);

}

}

}

private?static?boolean?isSafety(short[][]?chess,int?row,int?col)?{

//判斷中上、左上、右上是否安全

int?step=1;

while(row-step=0){

if(chess[row-step][col]==1) //中上

return?false;

if(col-step=0??chess[row-step][col-step]==1) //左上

return?false;

if(col+stepK??chess[row-step][col+step]==1) //右上

return?false;

step++;

}

return?true;

}

}

本文名稱：java代碼n皇后問題 n皇后問題c語言代碼
本文URL：http://vcdvsql.cn/article12/hehjdc.html

成都網站建設公司_創新互聯，為您提供電子商務、動態網站、網站營銷、搜索引擎優化、自適應網站、軟件開發

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯