java實現八皇后演算法,八皇后演算法實際應用

本文目錄一覽：

• 1、java八皇后問題
• 2、java：八皇后問題解題思路
• 3、JAVA中八皇后問題演算法和流程圖。要求用回溯法，求大神解答，在線等如果有代碼就完美了
• 4、誰能給我一個JAVA的八皇后的代碼(加上詳細的註解) 謝謝

java八皇后問題

希望我解釋的你能明白：

把棋盤看成二維方陣，行從上到下編號0-7（就是i），列從左到右編號0-7（就是j），這樣棋盤上每個點都可以表示為（i，j）

從鍵盤的右上角（0，7）到左下角（7，0）的對角線，以及這條線的平行線，就是反對角線，也就是這個程序里的undiagonal。顯然這個反對角線上任意2點（i1，j1）和（i2，j2）都滿足i1+j1=i2+j2.因為i+j可能的取值範圍是從0到14，所以把這個數組的長度定義為16（事實上15就可以了）

從鍵盤的左上角（0，0）到右下角（7，7）的對角線以及平行線，就是對角線，就是diagonal。同理，這個對角線及其平行線上任意2點都滿足i1-i2=j1-j2.i-j的範圍是-7到7，為了避免出現負數，程序里在這裡+7，也是一個長度為16的數組（還是15就夠了）

程序一開始的時候，i=j=0，所有的安全標識都是true，所以（0，0）這個點會被輸出。這時，把diagonal【7】置為false。因為（1，1），（2，2）等等這些點都和（0，0）在一條對角線上（因為0-0+7=1-1+7=2-2+7），所以把這些點的對應的diagonal都置為false，也就是把diagonal【7】置為false

並且把undiagonal【0】也置為false，但是因為undiagonal【0】對應的元素只有（0，0）（因為只有0+0=0），所以這個對這一步沒什麼影響。

然後一點點遞推，回溯，步驟就是這樣。希望你看得懂，如果不明白的話給我發消息吧

java：八皇后問題解題思路

遞歸：

首先每一行放置均會循環，也就是每一行的皇后都會被依次放置在8個位置上；

1）第一行在第一個位置上放置1枚皇后；

2）第二行在第一個位置上放置皇后，如果與已有的皇后不在一條直線上，則進入下一行，否則位置+1;

3）餘下幾行均依照步驟2）的方法進行放置，當最後一行放置好，列印輸出；

可以寫個函數，EightQueen（int

n,

int

*Pos）,其中n表示第幾行，Pos指向一個數組，Pos[i]=j表示第i行的位置是j；EightQueen（int

n,

int

*Pos）從n=1開始遞歸，到n=8遞歸結束。

代碼就不寫了，沒寫過java，寫不來

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

[cpp] view plaincopyprint?

//————————————–

//利用函數遞歸，解決八皇后問題

//

// zssure 2014-03-12

//————————————–

#include stdio.h

#include cmath

int count=0;//全局計數變數

/*——————–四個皇后———————-*/

//#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 };

/*——————–五個皇后———————-*/

//#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 };

/*——————–六個皇后———————-*/

//#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

// };

/*——————–七個皇后———————-*/

//#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

// };

/*——————–八個皇后———————-*/

#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))//對角區域填充

{

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/*皇后個數*/,int c/*已經放置的皇后個數*/)

{

//static int count=0;

//小於3×3的棋盤是無解的

if(n4)

return false;

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

{

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

{

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

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

{

++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);

/*————————————————————————————————————————-

// 現場恢復，無論下一個皇后是否順利放置，都應該恢復現場。原因是

//

// 如果下一個皇后放置失敗，那麼自然應該將本次放置的皇后去除，重新放置，所以需要進行現場恢復（即回溯）；

// 如果下一個皇后放置成功，意味著本次放置已經滿足條件，是一個解，此時需要恢復現場，進行下一次的重新放置，尋找下一個解。

//

//————————————————————————————————————————*/

//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;

}

誰能給我一個JAVA的八皇后的代碼(加上詳細的註解) 謝謝

public class Queen {

int num; //記錄方案數

int[]queenline=new int[8]; // 記錄8個皇后所佔用的列號

boolean[] col=new boolean[8]; //列安全標誌

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

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

void solve(int i)

{

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

{

if(col[j]diagonal[i-j+7]undiagonal[i+j]) //表示第i行第j列是安全的可以放皇后

{

queenline[i-1]=j+1;

col[j]=false; //修改安全標誌

diagonal[i-j+7]=false;

undiagonal[i+j]=false;

if(i8) //判斷是否放完8個皇后

{

solve(i+1); //未放完8個皇后則繼續放下一個

}

else //已經放完8個皇后

{

num++;

System.out.println(“\n皇后擺放第”+num+”種方案:”);

System.out.println(“行分別為1 2 3 4 5 6 7 8 列分別為”);

for(int i1=0;i18;i1++)

System.out.print(queenline[i1]+” “);

}

col[j]=true; //修改安全標誌，回溯

diagonal[i-j+7]=true;

undiagonal[i+j]=true;

}

}

}

public static void main(String[]args)

{

Queen q=new Queen();

System.out.println(“////////////////////////////八皇后問題////////////////////////////////”);

System.out.println(“在8行8列的棋盤上放置8個皇后,皇后可吃掉與她處於同行或同列或同一對角線上的其他棋子,使任一個皇后都不能吃掉其他的7個皇后共有92種方法”);

q.num=0; //方案初始化

for(int i=0;i8;i++) //置所有列為安全

q.col[i]=true;

for(int i0=0;i016;i0++) //置所有對角線為安全

q.diagonal[i0]=q.undiagonal[i0]=true;

q.solve(1);

}

}