java八皇后問(wèn)題

希望我解釋的你能明白：

成都網(wǎng)絡(luò)公司-成都網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián)公司十年經(jīng)驗(yàn)成就非凡，專業(yè)從事成都網(wǎng)站制作、網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)，成都網(wǎng)頁(yè)設(shè)計(jì)，成都網(wǎng)頁(yè)制作，軟文平臺(tái)，廣告投放等。十年來(lái)已成功提供全面的成都網(wǎng)站建設(shè)方案，打造行業(yè)特色的成都網(wǎng)站建設(shè)案例，建站熱線：13518219792，我們期待您的來(lái)電！

把棋盤(pán)看成二維方陣，行從上到下編號(hào)0-7（就是i），列從左到右編號(hào)0-7（就是j），這樣棋盤(pán)上每個(gè)點(diǎn)都可以表示為（i，j）

從鍵盤(pán)的右上角（0，7）到左下角（7，0）的對(duì)角線，以及這條線的平行線，就是反對(duì)角線，也就是這個(gè)程序里的undiagonal。顯然這個(gè)反對(duì)角線上任意2點(diǎn)（i1，j1）和（i2，j2）都滿足i1+j1=i2+j2.因?yàn)閕+j可能的取值范圍是從0到14，所以把這個(gè)數(shù)組的長(zhǎng)度定義為16（事實(shí)上15就可以了）

從鍵盤(pán)的左上角（0，0）到右下角（7，7）的對(duì)角線以及平行線，就是對(duì)角線，就是diagonal。同理，這個(gè)對(duì)角線及其平行線上任意2點(diǎn)都滿足i1-i2=j1-j2.i-j的范圍是-7到7，為了避免出現(xiàn)負(fù)數(shù)，程序里在這里+7，也是一個(gè)長(zhǎng)度為16的數(shù)組（還是15就夠了）

程序一開(kāi)始的時(shí)候，i=j=0，所有的安全標(biāo)識(shí)都是true，所以（0，0）這個(gè)點(diǎn)會(huì)被輸出。這時(shí)，把diagonal【7】置為false。因?yàn)椋?，1），（2，2）等等這些點(diǎn)都和（0，0）在一條對(duì)角線上（因?yàn)?-0+7=1-1+7=2-2+7），所以把這些點(diǎn)的對(duì)應(yīng)的diagonal都置為false，也就是把diagonal【7】置為false

并且把undiagonal【0】也置為false，但是因?yàn)閡ndiagonal【0】對(duì)應(yīng)的元素只有（0，0）（因?yàn)橹挥?+0=0），所以這個(gè)對(duì)這一步?jīng)]什么影響。

然后一點(diǎn)點(diǎn)遞推，回溯，步驟就是這樣。希望你看得懂，如果不明白的話給我發(fā)消息吧

八皇后問(wèn)題的java代碼。

boolean[] diagonal = new boolean[16]; // 對(duì)角線安全標(biāo)志

boolean[] undiagonal = new boolean[16]; // 反對(duì)角線安全標(biāo)志

用上兩個(gè)判斷是否能放置棋子

在 n 行 n 列的國(guó)際象棋棋盤(pán)上，最多可布n個(gè)皇后。

若兩個(gè)皇后位于同一行、同一列、同一對(duì)角線上，

則稱為它們?yōu)榛ハ喙簟?/p>

n皇后問(wèn)題是指找到這 n 個(gè)皇后的互不攻擊的布局。

n 行 n 列的棋盤(pán)上，主次對(duì)角線各有2n-1條。

利用行號(hào)i和列號(hào)j計(jì)算

主對(duì)角線編號(hào)k的方法是k = n+i-j-1；

計(jì)算次對(duì)角線編號(hào)k的方法是k = i+j

你主要是算法有些模糊罷了，現(xiàn)在我怕我說(shuō)的不好將你弄的越來(lái)越混亂所以給你個(gè)叫形象的若是還不明白，call me

package 百度;

//演示程序：n個(gè)皇后問(wèn)題

import java.io.*;

/*

在 n 行 n 列的國(guó)際象棋棋盤(pán)上，最多可布n個(gè)皇后。

若兩個(gè)皇后位于同一行、同一列、同一對(duì)角線上，

則稱為它們?yōu)榛ハ喙簟?/p>

n皇后問(wèn)題是指找到這 n 個(gè)皇后的互不攻擊的布局。

n 行 n 列的棋盤(pán)上，主次對(duì)角線各有2n-1條。

利用行號(hào)i和列號(hào)j計(jì)算

主對(duì)角線編號(hào)k的方法是k = n+i-j-1；

計(jì)算次對(duì)角線編號(hào)k的方法是k = i+j

*/

//"n個(gè)皇后問(wèn)題"之類定義

public class cQueen {

int n; //皇后問(wèn)題的大小

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

int md[]; //數(shù)組，各主對(duì)角線有無(wú)皇后(0，1)

int sd[]; //數(shù)組，各次對(duì)角線有無(wú)皇后(0，1)

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

int Q; //已布皇后數(shù)，計(jì)數(shù)

int r; //n皇后問(wèn)題的解的組數(shù)

//構(gòu)造函數(shù) n皇后問(wè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];

}

//函數(shù)：打印棋盤(pá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++; //解的組數(shù)

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

}

//求解n皇后問(wèn)題

/*

此函數(shù)試圖在n*n的棋盤(pán)的第i行上放一個(gè)皇后,

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

放另一個(gè)皇后,若第i行是最后一行，則打印棋盤(pán)。

*/

public void resolve(int i) {

int j;

// 在第i行給定后檢查棋盤(pán)上的每一列

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

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

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

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

// 標(biāo)記新布皇后的攻擊范圍

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

// 如果已經(jīng)布了n個(gè)皇后（得到了一組解）,

// 把棋盤(pán)（解）打印出來(lái)。

if(Q==n) showBoard();

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

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

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

else resolve(0); //因?yàn)榧s定起始行可以任選

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

//并消除所標(biāo)記的攻擊范圍，為回溯作準(zhǔn)備。

Q--; q[i]=0;

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

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

}

} //下一列，j循環(huán)

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

}

//輸出解的個(gè)數(shù)

public void HowMany() {

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

}

//主方法main()

public static void main(String []args) {

//定義一個(gè)8皇后問(wèn)題（有92組解）

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

//第一個(gè)皇后可以在任意一行布放

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

Q1.HowMany();

}

} //類Queen定義結(jié)束

關(guān)于看代碼的人人都知道的小技巧，最小試探法來(lái)輸出結(jié)果進(jìn)行比較和分析

救助八皇后JAVA程序代碼

public class demo {

public static int N = 0;

public static int ROW = 8;

public int[][] chase = new int[demo.ROW][demo.ROW];

public demo() {

for (int i = 0; i demo.ROW; i++)

for (int j = 0; j demo.ROW; j++)

chase[i][j] = 0;

}

public void copy(int[][] k, int[][] l) {

for (int i = 0; i demo.ROW; i++)

for (int j = 0; j demo.ROW; j++)

l[i][j] = k[i][j];

}

public void changeChase(int[][] chase, int row, int i) {

for (int j = 1; j demo.ROW; j++) {

chase[row][j] = 1;

chase[j][i] = 1;

}

for (int j = 1; j demo.ROW; j++) {

if (row - j = 0 i - j = 0)

chase[row - j][i - j] = 1;

if (row + j = 7 i - j = 0)

chase[row + j][i - j] = 1;

if (row - j = 0 i + j = 7)

chase[row - j][i + j] = 1;

if (row + j = 7 i + j = 7)

chase[row + j][i + j] = 1;

}

chase[row][i] = 2;

}

public void putout(int[][] chase) {

for (int i = 0; i demo.ROW; i++) {

for (int j = 0; j demo.ROW; j++)

System.out.print(chase[i][j] + " ");

System.out.println();

}

}

public void putQueen(int row, int[][] m) {

if (row == 8) {

System.out.println("this is the" + demo.N++ + "個(gè)答案:");

putout(m);

} else {

for (int i = 0; i 8; i++) {

if (m[row][i] == 0) {

int[][] l = new int[demo.ROW][demo.ROW];

copy(m, l);

changeChase(l, row, i);

putQueen(row + 1, l);

}

}

}

}

public static void main(String[] Args) {

demo Q = new demo();

Q.putQueen(0, Q.chase);

}

}

JAVA中八皇后問(wèn)題算法和流程圖。要求用回溯法，求大神解答，在線等如果有代碼就完美了

[cpp] view plaincopyprint?

//--------------------------------------

//利用函數(shù)遞歸，解決八皇后問(wèn)題

//

// zssure 2014-03-12

//--------------------------------------

#include stdio.h

#include cmath

int count=0;//全局計(jì)數(shù)變量

/*--------------------四個(gè)皇后----------------------*/

//#define QUEEN_NUM 4

//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,

// 0,0,0,0,

// 0,0,0,0,

// 0,0,0,0 };

/*--------------------五個(gè)皇后----------------------*/

//#define QUEEN_NUM 5

//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,0,

// 0,0,0,0,0,

// 0,0,0,0,0,

// 0,0,0,0,0,

// 0,0,0,0,0 };

/*--------------------六個(gè)皇后----------------------*/

//#define QUEEN_NUM 6

//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,0,0,

// 0,0,0,0,0,0,

// 0,0,0,0,0,0,

// 0,0,0,0,0,0,

// 0,0,0,0,0,0,

// 0,0,0,0,0,0

// };

/*--------------------七個(gè)皇后----------------------*/

//#define QUEEN_NUM 7

//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,0,0,0,

// 0,0,0,0,0,0,0,

// 0,0,0,0,0,0,0,

// 0,0,0,0,0,0,0,

// 0,0,0,0,0,0,0,

// 0,0,0,0,0,0,0,

// 0,0,0,0,0,0,0

// };

/*--------------------八個(gè)皇后----------------------*/

#define QUEEN_NUM 8

int label[QUEEN_NUM][QUEEN_NUM]={0,0,0,0,

0,0,0,0,

0,0,0,0,

0,0,0,0,

0,0,0,0,

0,0,0,0,

0,0,0,0,

0,0,0,0,

0,0,0,0,

0,0,0,0,

0,0,0,0,

0,0,0,0,

0,0,0,0,

0,0,0,0,

0,0,0,0,

0,0,0,0};

void FillChessbox(int m,int n,int num)

{

for(int i=0;iQUEEN_NUM;++i)

for(int j=0;jQUEEN_NUM;++j)

if(abs(i-m)==abs(j-n))//對(duì)角區(qū)域填充

{

if(label[i][j]==0)

label[i][j]=num;

}

int i=0,j=0;

while(iQUEEN_NUM)//行填充

{

if(label[i][n]==0)

label[i][n]=num;

++i;

}

while(jQUEEN_NUM)//列填充

{

if(label[m][j]==0)

label[m][j]=num;

++j;

}

}

void ClearChessBox(int m,int n,int num)

{

for(int i=0;iQUEEN_NUM;++i)

for(int j=0;jQUEEN_NUM;++j)

if(abs(i-m)==abs(j-n) label[i][j]==num)

label[i][j]=0;

int i=0,j=0;

while(iQUEEN_NUM)

{

if(label[i][n]==num)

label[i][n]=0;

++i;

}

while(jQUEEN_NUM)

{

if(label[m][j]==num)

label[m][j]=0;

++j;

}

}

void AllClear()

{

for(int i=0;iQUEEN_NUM;++i)

for(int j=0;jQUEEN_NUM;++j)

label[i][j]=0;

}

void PrintResult()

{

for(int i=0;iQUEEN_NUM;++i)

{

for(int j=0;jQUEEN_NUM;++j)

printf("%d ",label[i][j]);

printf("\n");

}

}

bool EightQueen(int n/*皇后個(gè)數(shù)*/,int c/*已經(jīng)放置的皇后個(gè)數(shù)*/)

{

//static int count=0;

//小于3x3的棋盤(pán)是無(wú)解的

if(n4)

return false;

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

{

if(label[c-1][i]==0)//存在可以放置第c個(gè)皇后的位置

{

label[c-1][i]=c+1;

if(c==n)/*已經(jīng)放置完畢所有的皇后*/

{

++count;

PrintResult();

printf("**************************\n");

ClearChessBox(c-1,i,c+1);

//AllClear();

return true;

}

FillChessbox(c-1,i,c+1);

EightQueen(n,c+1);

ClearChessBox(c-1,i,c+1);

/*-------------------------------------------------------------------------------------------------------------------------

// 現(xiàn)場(chǎng)恢復(fù)，無(wú)論下一個(gè)皇后是否順利放置，都應(yīng)該恢復(fù)現(xiàn)場(chǎng)。原因是

//

// 如果下一個(gè)皇后放置失敗，那么自然應(yīng)該將本次放置的皇后去除，重新放置，所以需要進(jìn)行現(xiàn)場(chǎng)恢復(fù)（即回溯）；

// 如果下一個(gè)皇后放置成功，意味著本次放置已經(jīng)滿足條件，是一個(gè)解，此時(shí)需要恢復(fù)現(xiàn)場(chǎng)，進(jìn)行下一次的重新放置，尋找下一個(gè)解。

//

//------------------------------------------------------------------------------------------------------------------------*/

//if(!EightQueen(n,c+1))

// ClearChessBox(c-1,i,c+1);

}

}

return false;

}

int main()

{

EightQueen(QUEEN_NUM,1);

printf("%d\n",count);

return 0;

}

文章名稱：8個(gè)皇后的java的代碼的簡(jiǎn)單介紹
分享路徑：http://vcdvsql.cn/article14/dopjpde.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計(jì)、網(wǎng)站設(shè)計(jì)公司、企業(yè)網(wǎng)站制作、品牌網(wǎng)站制作、服務(wù)器托管、電子商務(wù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)