java八皇後
Ⅰ 求java八皇後問題代碼
別人的代碼 你看看吧
//8 Queen 遞歸演算法
//如果有一個Q 為 chess[i]=j;
//則不安全的地方是 k行 j位置,j+k-i位置,j-k+i位置
class Queen8{
static final int QueenMax = 8;
static int oktimes = 0;
static int chess[] = new int[QueenMax];//每一個Queen的放置位置
public Queen8(){
for (int i=0;i<QueenMax;i++)chess[i]=-1;
placequeen(0);
System.out.println("八皇後共有"+oktimes+"個解法");
}
public static void placequeen(int num){ //num 為現在要放置的行數
int i=0;
boolean qsave[] = new boolean[QueenMax];
for(;i<QueenMax;i++) qsave[i]=true;
//下面先把安全位數組完成
i=0;//i 是現在要檢查的數組值
while (i<num){
qsave[chess[i]]=false;
int k=num-i;
if ( (chess[i]+k >= 0) && (chess[i]+k < QueenMax) ) qsave[chess[i]+k]=false;
if ( (chess[i]-k >= 0) && (chess[i]-k < QueenMax) ) qsave[chess[i]-k]=false;
i++;
}
//下面歷遍安全位
for(i=0;i<QueenMax;i++){
if (qsave[i]==false)continue;
if (num<QueenMax-1){
chess[num]=i;
placequeen(num+1);
}
else{ //num is last one
chess[num]=i;
oktimes++;
System.out.println("這是第"+oktimes+"個解法 如下:");
System.out.println("第n行: 1 2 3 4 5 6 7 8");
for (i=0;i<QueenMax;i++){
String row="第"+(i+1)+"行：";
if (chess[i]==0);
else
for(int j=0;j<chess[i];j++) row+="--";
row+="++";
int j = chess[i];
while(j<QueenMax-1){row+="--";j++;}
System.out.println(row);
}
}
}
//歷遍完成就停止
}
public static void main(String args[]){
Queen8 quee8=new Queen8();
}
Ⅱ java 八皇後問題 遞歸 回溯
你main方法也沒有加上，這樣吧，我給你看代碼，這個比較容易理解。
packagecom.aice.queen;
publicclassQueen{
//同欄是否有皇後，1表示有
privateint[]column;
//右上至左下是否有皇後
privateint[]rup;
//左上至右下是否有皇後
privateint[]lup;
//解答
privateint[]queen;
//解答編號
privateintnum;
publicQueen(){
column=newint[8+1];
rup=newint[(2*8)+1];
lup=newint[(2*8)+1];
for(inti=1;i<=8;i++)
column[i]=1;
for(inti=1;i<=(2*8);i++)
rup[i]=lup[i]=1;
queen=newint[8+1];
}
publicvoidbacktrack(inti){
if(i>8){
showAnswer();
}else{
for(intj=1;j<=8;j++){
if((column[j]==1)&&(rup[i+j]==1)&&
(lup[i-j+8]==1)){
queen[i]=j;
//設定為佔用
column[j]=rup[i+j]=lup[i-j+8]=0;
backtrack(i+1);
column[j]=rup[i+j]=lup[i-j+8]=1;
}
}
}
}
protectedvoidshowAnswer(){
num++;
System.out.println(" 解答"+num);
for(inty=1;y<=8;y++){
for(intx=1;x<=8;x++){
if(queen[y]==x){
System.out.print("Q");
}else{
System.out.print(".");
}
}
System.out.println();
}
}
publicstaticvoidmain(String[]args){
Queenqueen=newQueen();
queen.backtrack(1);
}
}
Ⅲ 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的八皇後的代碼(加上詳細的註解) 謝謝
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;j<8;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(i<8) //判斷是否放完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;i1<8;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;i<8;i++) //置所有列為安全
q.col[i]=true;
for(int i0=0;i0<16;i0++) //置所有對角線為安全
q.diagonal[i0]=q.undiagonal[i0]=true;
q.solve(1);
}
}
Ⅳ Java編程八皇後，但是第一個皇後是我們手動輸入的該怎麼編呢
明天或後天給你代碼
package algorithm;
public class Demo_3 {
/**八皇後問題：國際象棋棋盤有8行8列共64個單元格，在棋盤上放8個皇後，使其不能互相攻擊，也就是說任意兩個皇後不能處於同一行，同
* 一列或同一斜線上。問共有多少種擺放方法。每一種擺放方式是怎麼樣的？
* @param args
*/
static int count = 0;
static int[] location = new int[8];
public static void Output()
{
int i, j, flag = 1;
System.out.printf("第%2d種方案（Q表示皇後）：\n", ++count);
System.out.printf(" ");
for(i = 1; i <= 8; i ++)
{
System.out.printf("_");
}
System.out.printf("\n");
for(i = 0; i < 8; i ++)
{
System.out.printf(" |");
for(j = 0; j < 8; j ++)
{
if(location[i] - 1 == j)
{
System.out.printf("Q"); //皇後的位置
}else
{
if(flag < 0)
{
System.out.printf(" "); //棋格
}else
{
System.out.printf("×"); //棋格
}
}
flag = -1 * flag;
}
System.out.printf("| \n");
flag = -1 * flag;
}
System.out.printf(" ");
for(i = 1; i <= 8; i ++)
{
System.out.printf("-");
}
System.out.printf("\n");
}
static void EightQueen(int n) //演算法
{
int i, j;
int ct; //用於判斷是否沖突
if(n == 8) //若8個皇後已放置完成
{
Output(); //輸出求解結果是
return;
}
for(i = 1; i <= 8; i++)
{
location[n] = i ; //在該列的第i行上放置
//判斷第n個皇後是否與前面皇後形成攻擊
ct = 1;
for(j = 0; j < n; j ++)
{
if(location[j] == location[n]) //形成攻擊
{
ct = 0;
}else if(Math.abs(location[j] - location[n]) == (n - j)) //形成攻擊的
{
ct = 0;
}
}
if(ct == 1) //沒有沖突，就開始下一列的試探
{
EightQueen(n+1); //遞歸調用
}
}
}
public static void main(String[] args)
{
System.out.printf("八皇後問題求解!\n");
System.out.printf("八皇後排列方式：\n");
EightQueen(0);
}
}
Ⅵ 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(i>8){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);}}
Ⅶ 八皇後問題的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;i<n;i++) {
for(j=0;j<n;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;j<n;j++) {
//如果在第i行的第j列可以布放皇後
if(col[j]==0&&md[n+i-j-1]==0&&sd[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(i<n-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定義結束
關於看代碼的人人都知道的小技巧，最小試探法來輸出結果進行比較和分析
Ⅷ JAVA中八皇後問題演算法和流程圖。要求用回溯法，求大神解答，在線等如果有代碼就完美了
[cpp] view plainprint?
//--------------------------------------
//利用函數遞歸，解決八皇後問題
//
// 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;i<QUEEN_NUM;++i)
for(int j=0;j<QUEEN_NUM;++j)
if(abs(i-m)==abs(j-n))//對角區域填充
{
if(label[i][j]==0)
label[i][j]=num;
}
int i=0,j=0;
while(i<QUEEN_NUM)//行填充
{
if(label[i][n]==0)
label[i][n]=num;
++i;
}
while(j<QUEEN_NUM)//列填充
{
if(label[m][j]==0)
label[m][j]=num;
++j;
}
}
void ClearChessBox(int m,int n,int num)
{
for(int i=0;i<QUEEN_NUM;++i)
for(int j=0;j<QUEEN_NUM;++j)
if(abs(i-m)==abs(j-n) && label[i][j]==num)
label[i][j]=0;
int i=0,j=0;
while(i<QUEEN_NUM)
{
if(label[i][n]==num)
label[i][n]=0;
++i;
}
while(j<QUEEN_NUM)
{
if(label[m][j]==num)
label[m][j]=0;
++j;
}
}
void AllClear()
{
for(int i=0;i<QUEEN_NUM;++i)
for(int j=0;j<QUEEN_NUM;++j)
label[i][j]=0;
}
void PrintResult()
{
for(int i=0;i<QUEEN_NUM;++i)
{
for(int j=0;j<QUEEN_NUM;++j)
printf("%d ",label[i][j]);
printf("\n");
}
}
bool EightQueen(int n/*皇後個數*/,int c/*已經放置的皇後個數*/)
{
//static int count=0;
//小於3x3的棋盤是無解的
if(n<4)
return false;
for(int i=0;i<n;++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：八皇後問題解題思路
遞歸：
首先每一行放置均會循環，也就是每一行的皇後都會被依次放置在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八皇後問題的實驗報告
http://blog.itweb2.com/article.asp?id=140
*
* 8皇後問題：
*
* 問題描述：
* 在一個8×8的棋盤里放置8個皇後，要求每個皇後兩兩之間不相沖突
*（在每一橫列，豎列，斜列只有一個皇後）。
*
* 數據表示：
* 用一個 8 位的 8 進制數表示棋盤上皇後的位置：
* 比如：45615353 表示：
* 第0列皇後在第4個位置
* 第1列皇後在第5個位置
* 第2列皇後在第6個位置
* 。。。
* 第7列皇後在第3個位置
*
* 循環變數從 00000000 加到 77777777 （8進制數）的過程，就遍歷了皇後所有的情況
* 程序中用八進制數用一個一維數組 data[] 表示
*
* 檢測沖突：
* 橫列沖突：data == data[j]
* 斜列沖突：(data+i) == (data[j]+j) 或者 (data-i) == (data[j]-j)
*
* 好處：
* 採用循環，而不是遞規，系統資源佔有少
* 可計算 n 皇後問題
* 把問題線性化處理，可以把問題分塊，在分布式環境下用多台計算機一起算。
*
* ToDo：
* 枚舉部分還可以進行優化，多加些判斷條件速度可以更快。
* 輸出部分可以修改成棋盤形式的輸出
*
* @author cinc 2002-09-11
*
*/
public class Queen {
int size;
int resultCount;
public void compute ( int size ) {
this.size = size;
resultCount = 0;
int data[] = new int[size];
int count; // 所有可能的情況個數
int i,j;
// 計算所有可能的情況的個數
count = 1;
for ( i=0 ; i<size ; i++ ) {
count = count * size;
}
// 對每一個可能的情況
for ( i=0 ; i<count ; i++ ) {
// 計算這種情況下的棋盤上皇後的擺放位置，用 8 進制數表示
// 此處可優化
int temp = i;
for ( j=0 ; j<size ; j++ ) {
data [j] = temp % size;
temp = temp / size;
}
// 測試這種情況是否可行，如果可以，輸出
if ( test(data) )
output( data );
}
}
/*
* 測試這種情況皇後的排列是否可行
*
*/
public boolean test( int[] data ) {
int i,j;
for ( i=0 ; i<size ; i++ ) {
for ( j=i+1 ; j<size ; j++ ) {
// 測試是否在同一排
if ( data == data[j] )
return false;
// 測試是否在一斜線
if ( (data+i) == (data[j]+j) )
return false;
// 測試是否在一反斜線
if ( (data-i) == (data[j]-j) )
return false;
}
}
return true;
}
/*
* 輸出某種情況下皇後的坐標
*
*/
public void output ( int[] data ) {
int i;
System.out.print ( ++resultCount + ": " );
for ( i=0 ; i<size ; i++ ) {
System.out.print ( "(" + i + "," + data + ") " );
}
System.out.println ();
}
public static void main(String args[]) {
(new Queen()).compute( 8 );
}
}