boolean[] diagonal = new boolean[16]; // 對(duì)角線安全標(biāo)志
創(chuàng)新互聯(lián)公司于2013年創(chuàng)立，先為科爾沁左翼等服務(wù)建站，科爾沁左翼等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為科爾沁左翼企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。
boolean[] undiagonal = new boolean[16]; // 反對(duì)角線安全標(biāo)志
用上兩個(gè)判斷是否能放置棋子
在 n 行 n 列的國際象棋棋盤上，最多可布n個(gè)皇后。
若兩個(gè)皇后位于同一行、同一列、同一對(duì)角線上，
則稱為它們?yōu)榛ハ喙簟?/p>
n皇后問題是指找到這 n 個(gè)皇后的互不攻擊的布局。
n 行 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)在我怕我說的不好將你弄的越來越混亂所以給你個(gè)叫形象的若是還不明白，call me
package 百度;
//演示程序：n個(gè)皇后問題
import java.io.*;
/*
在 n 行 n 列的國際象棋棋盤上，最多可布n個(gè)皇后。
若兩個(gè)皇后位于同一行、同一列、同一對(duì)角線上，
則稱為它們?yōu)榛ハ喙簟?/p>
n皇后問題是指找到這 n 個(gè)皇后的互不攻擊的布局。
n 行 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è)皇后問題"之類定義
public class cQueen {
int n; //皇后問題的大小
int col[]; //數(shù)組，各列上有無皇后(0，1)
int md[]; //數(shù)組，各主對(duì)角線有無皇后(0，1)
int sd[]; //數(shù)組，各次對(duì)角線有無皇后(0，1)
int q[]; //數(shù)組，第i行上皇后在第幾列(0,n-1)
int Q; //已布皇后數(shù)，計(jì)數(shù)
int r; //n皇后問題的解的組數(shù)
//構(gòu)造函數(shù) 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ù)：打印棋盤
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皇后問題
/*
此函數(shù)試圖在n*n的棋盤的第i行上放一個(gè)皇后,
若找到可以放的位置,就遞歸調(diào)用自身試圖在i+1行
放另一個(gè)皇后,若第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行皇后在第幾列
// 標(biāo)記新布皇后的攻擊范圍
col[j]=md[n+i-j-1]=sd[i+j]=1;
// 如果已經(jīng)布了n個(gè)皇后（得到了一組解）,
// 把棋盤（解）打印出來。
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+"皇后問題共有解"+r+"組。");
}
//主方法main()
public static void main(String []args) {
//定義一個(gè)8皇后問題（有92組解）
cQueen Q1=new cQueen(8); //大于10，你的微機(jī)可能要死機(jī)！
//第一個(gè)皇后可以在任意一行布放
Q1.resolve(0); //參數(shù)在0到n-1之間任選
Q1.HowMany();
}
} //類Queen定義結(jié)束
關(guān)于看代碼的人人都知道的小技巧，最小試探法來輸出結(jié)果進(jìn)行比較和分析
希望我解釋的你能明白：
把棋盤看成二維方陣，行從上到下編號(hào)0-7（就是i），列從左到右編號(hào)0-7（就是j），這樣棋盤上每個(gè)點(diǎn)都可以表示為（i，j）
從鍵盤的右上角（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ù)組的長度定義為16（事實(shí)上15就可以了）
從鍵盤的左上角（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è)長度為16的數(shù)組（還是15就夠了）
程序一開始的時(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ā)消息吧
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);
}
}
重慶分公司
重慶分公司
