明天或后天給你代碼
創(chuàng)新互聯(lián)是一家專業(yè)從事網(wǎng)站制作、網(wǎng)站設(shè)計(jì)的網(wǎng)絡(luò)公司。作為專業(yè)網(wǎng)絡(luò)公司,創(chuàng)新互聯(lián)依托的技術(shù)實(shí)力、以及多年的網(wǎng)站運(yùn)營(yíng)經(jīng)驗(yàn),為您提供專業(yè)的成都網(wǎng)站建設(shè)、網(wǎng)絡(luò)營(yíng)銷推廣及網(wǎng)站設(shè)計(jì)開(kāi)發(fā)服務(wù)！
package algorithm;
public class Demo_3 {
/**八皇后問(wèn)題：國(guó)際象棋棋盤有8行8列共64個(gè)單元格，在棋盤上放8個(gè)皇后，使其不能互相攻擊，也就是說(shuō)任意兩個(gè)皇后不能處于同一行，同
* 一列或同一斜線上。問(wèn)共有多少種擺放方法。每一種擺放方式是怎么樣的？
* @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個(gè)皇后已放置完成
{
Output(); //輸出求解結(jié)果是
return;
}
for(i = 1; i = 8; i++)
{
location[n] = i ; //在該列的第i行上放置
//判斷第n個(gè)皇后是否與前面皇后形成攻擊
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) //沒(méi)有沖突，就開(kāi)始下一列的試探
{
EightQueen(n+1); //遞歸調(diào)用
}
}
}
public static void main(String[] args)
{
System.out.printf("八皇后問(wèn)題求解!\n");
System.out.printf("八皇后排列方式：\n");
EightQueen(0);
}
}
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);
}
}
希望我解釋的你能明白：
把棋盤看成二維方陣，行從上到下編號(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ù)組的長(zhǎng)度定義為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è)長(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ā)消息吧
boolean[] diagonal = new boolean[16]; // 對(duì)角線安全標(biāo)志
boolean[] undiagonal = new boolean[16]; // 反對(duì)角線安全標(biāo)志
用上兩個(gè)判斷是否能放置棋子
在 n 行 n 列的國(guó)際象棋棋盤上，最多可布n個(gè)皇后。
若兩個(gè)皇后位于同一行、同一列、同一對(duì)角線上，
則稱為它們?yōu)榛ハ喙簟?/p>
n皇后問(wè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)在我怕我說(shuō)的不好將你弄的越來(lái)越混亂所以給你個(gè)叫形象的若是還不明白，call me
package 百度;
//演示程序：n個(gè)皇后問(wèn)題
import java.io.*;
/*
在 n 行 n 列的國(guó)際象棋棋盤上，最多可布n個(gè)皇后。
若兩個(gè)皇后位于同一行、同一列、同一對(duì)角線上，
則稱為它們?yōu)榛ハ喙簟?/p>
n皇后問(wè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è)皇后問(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ù)：打印棋盤
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的棋盤的第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è)皇后（得到了一組解）,
// 把棋盤（解）打印出來(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)行比較和分析
你main方法也沒(méi)有加上，這樣吧，我給你看代碼，這個(gè)比較容易理解。
package?com.aice.queen;
public?class?Queen{
//同欄是否有皇后，1表示有
private?int[]column;
?
//右上至左下是否有皇后
private?int[]rup;
?
//左上至右下是否有皇后
private?int[]lup;
?
//解答
private?int[]queen;
?
//解答編號(hào)
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]=1;
for(int?i?=?1;i=(2*8);i++)
rup[i]?=?lup[i]?=?1;
queen?=?new?int[8+1];
}
public?void?backtrack(int?i){
if(i8){
showAnswer();
}else{
for(int?j=1;j=8;j++){
if((column[j]==1)(rup[i+j]==1)
(lup[i-j+8]==1)){
queen[i]=j;
//設(shè)定為占用
column[j]=rup[i+j]=lup[i-j+8]=0;
backtrack(i+1);
column[j]=rup[i+j]=lup[i-j+8]=1;
}
}
}
}
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);
}
}
public class Queen{//同欄是否有皇后，1表示有private int[] column;//右上至左下是否有皇后private int[] rup;//左上至右下是否有皇后private int[] lup;//解答private int[] queen;//解答編號(hào)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; //初始定義全部無(wú)皇后 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)){//若無(wú)皇后queen[i]=j;//設(shè)定為占用column[j]=rup[i+j]=lup[i-j+8]=1;backtrack(i+1); //循環(huán)調(diào)用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);}}
重慶分公司
重慶分公司
