四皇后java（四皇后問題圖解）

本文目錄一覽：

1、八皇后問題的java代碼。
2、用VB的窮舉法解決四皇后問題，急！
3、JAVA中八皇后問題演算法和流程圖。要求用回溯法，求大神解答，在線等如果有代碼就完美了
4、9.2 回溯演算法的例子
5、C語言四皇后問題
6、Java編程八皇后，但是第一個皇后是我們手動輸入的該怎麼編呢

八皇后問題的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;in;i++) {

for(j=0;jn;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;jn;j++) {

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

if(col[j]==0md[n+i-j-1]==0sd[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(in-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定義結束

關於看代碼的人人都知道的小技巧，最小試探法來輸出結果進行比較和分析

用VB的窮舉法解決四皇后問題，急！

Private Sub Command1_Click()

For i = 1 To 4

For j = 1 To 4

If i j Then

For k = 1 To 4

If i k And j k Then

For l = 1 To 4

If i l And j l And k l Then

If (i + 1 j And i + 2 k And i + 3 l) And (j + 1 k And j + 2 l) And k + 1 l And _

(i – 1 j And i – 2 k And i – 3 l) And (j – 1 k And j – 2 l) And k – 1 l Then

Print “(“; i; “,1)”, “(“; j; “,2)”, “(“; k; “,3)”, “(“; l; “,4)”

End If

Next l

End If

Next k

End If

Next j, i

End Sub

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

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

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

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

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

// };

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

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

// };

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

#define QUEEN_NUM 8

int label[QUEEN_NUM][QUEEN_NUM]={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;

}

9.2 回溯演算法的例子

在4 * 4的方格棋盤上放置4個皇后棋子，使得沒有兩個皇后在同一行、同一列，也不在同一條45度的斜線上，問有多少種布局?

回溯演算法的解一般是向量，而這個題也不例外，設4維向量的x1,x2,x3,x4，Xi中i表示第幾個皇后，Xi表示在棋盤第i行的位置，比如其中一個解是2,4,1,3，如下圖

1.四皇后問題中，葉節點就是一個解。

2.四皇后每一個節點的子樹代表著下一個皇后可以放的列數，因為都是n，所以子樹都是n叉樹，故四皇后是一顆 n叉樹

3.四皇后的解至少有兩個，因為棋盤可以沿著中心線翻折

有n種物品，每種物品只有1個。第i種物品價值為vi，重量為wi，i=1，2，3…n. 問如何選擇放入背包的物品，使得總重量不超過B，而價值達到最大?

同樣，此問題的解可用一個向量來表示，該向量就代表了所有的物品，如果對應物品為1，則表示裝入背包，反之，沒有被裝入。

因此，回溯的每層可以表示為對應的物品，分支左右可以表示取或者不取（向量中表示為1或0）

總而言之，每一個節點也就是物品只有0和1兩種狀態，因此該樹一棵二叉樹，或者為子集樹

1.選擇第一個物品，目前總重量為8，總價值為12。

2.再選擇第二個物品，總重量為14 13，觸發回溯。

3.不選擇第二個物品，選擇第三個商品，總重量是12，總價值為21。

4.再選擇第四個物品，總重量為15 13，觸發回溯。

5.不選擇第四個物品，總重量為12，總價值為21，與目前最優解價值進行比較，如果最優解價值大於21則替換目前的最優解向量和最優解價值。

1.背包問題只有在葉節點才能生成一個滿足條件的解，而之後將該解和最優解比較。

2.背包問題必須遍歷完所有的分支，才能夠獲得最終的解。

3.背包問題是一顆子集樹。

有n個城市，已知任兩個城市之間的距離，求一條每個城市恰好經過一次的迴路，使得總長度最小。

貨郎問題中主要的一點就是每一個點（除了第一個點）其他點必須經過且只能經過1次，這就很像數學中的排列。

因此，我們採用一個向量來表示貨郎問題的城市排列

1.貨郎問題是一顆分支不斷減少的排列數（和數學的排列類似）

2.貨郎問題也得遍歷完所有的情況，比較後得出最優解。

1.解都是用向量表示

2.搜索空間都是樹

3.搜索策略多種，有深度優先、寬度優先和跳躍式遍歷搜索樹。

C語言四皇后問題

//title：4皇后問題的回溯演算法求解

//Demo: 1）回溯演算法實現4皇后問題；2）難點：樹形結構的表達；3）用線性容器表達樹形結構，並實現樹的掃描??降低了樹實現的難度

//author: Liping Chen

//email: alaclp@qq.com

//published date: 20125-4-11

#include iostream

#include string.h

#include vector

#include stdlib.h

using namespace std;

//定義4皇后棋局的數據結構及方法

typedef struct Queen4 {

int vals[16];

int nQueens;

int parent;

//默認構造函數

Queen4() {

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

vals[i] = 0;

parent = 0;

nQueens = 0;

}

//構造函數1

Queen4(int nvals[16]) {

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

vals[i] = nvals[i];

parent = 0;

nQueens = 0;

}

//找到當前布局中不為0的位置

int getPosition() {

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

if (vals[i] == 0) {

return i;

}

return -1;

}

//當設置皇后位置時，標記水平、垂直和斜線位置掩碼

void setQueen(int pos) {

int row, col;

vals[pos] = 1;

nQueens++;

row = pos / 4;

col = pos % 4;

for(int c = 1; c = 3; c++) {

//右下

if (row + c 4 col + c 4)

if (vals[(row + c) * 4 + (col + c)] == 0)

vals[(row + c) * 4 + (col + c)] = 2;

//左上

if (row – c = 0 col – c = 0)

if (vals[(row – c) * 4 + (col – c)] == 0)

vals[(row – c) * 4 + (col – c)] = 2;

//左下

if (row + c 4 col – c = 0)

if (vals[(row + c) * 4 + (col – c)] == 0)

vals[(row + c) * 4 + (col – c)] = 2;

//右上

if (row – c = 0 col + c = 0)

if (vals[(row – c) * 4 + (col + c)] == 0)

vals[(row – c) * 4 + (col + c)] = 2;

//右水平

if (col + c 4)

if (vals[row * 4 + (col + c)] == 0)

vals[row * 4 + (col + c)] = 2;

//左水平

if (col – c = 0)

if (vals[row * 4 + (col – c)] == 0)

vals[row * 4 + (col – c)] = 2;

//下

if (row + c 4)

if (vals[(row + c) * 4 + col] == 0)

vals[(row + c) * 4 + col] = 2;

//上

if (row – c = 0)

if (vals[(row – c) * 4 + col] == 0)

vals[(row – c) * 4 + col] = 2;

}

//輸出當前棋局

void output(int level) {

int cnt = 0;

char chars[100];

for(int k = 0; k level; k++)

chars[k] = ‘ ‘;

chars[level] = ‘\0’;

cout chars “Queen4=” endl chars;

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

cout vals[i] ” “;

cnt++;

if (cnt % 4 == 0) cout endl chars;

}

//遞歸調用輸出歷史棋局

void outputHist(vectorQueen4 tr) {

if (parent)

tr[parent].outputHist(tr);

output(0);

}

//由棋的當前布局產生下一布局

void reproduce(vectorQueen4 tr, int pos) {

int nvals[16];

bool inserted;

//思考：為什麼要使用nvals

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

nvals[i] = vals[i];

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

if (nvals[i] == 0) {

nvals[i] = 1;

//新結果加入容器

Queen4 q(tr[pos].vals);

q.setQueen(i);

q.parent = pos;

tr.push_back(q);

}

}Queen4;

//程序主函數

int main() {

Queen4 q0; //調用默認構造函數

vectorQueen4 tr; //向量容器??作用相當於隊列，可以向期中添加新的棋盤布局

int levels[1024] = {0}; //記錄每層的孩子數量??用於分層

tr.push_back(q0); //將初始棋盤加入容器

int oldn = 0, newn = 1, level = 0; //存儲變數

//讓根節點產生新孩子，並把新孩子加入容器

//若不再產生新孩子了，則認為已找到答案

//那麼，最底層的就是答案（需要記錄每層所產生的孩子數）

while(newn != oldn) {

//讓最後的孩子再產生新孩子

for(int i = oldn; i newn; i++) tr[i].reproduce(tr, i);

//更新老孩子和新孩子的數量

oldn = newn;

levels[++level] = newn;

newn = tr.size();

}

oldn = 1;

//輸出4皇后問題共有多少種解法

for(int i = levels[level-1]; i levels[level]; i++) {

cout “4皇后放置走法：” oldn++ endl;

tr[i].outputHist(tr);

}

return 0;

}

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

}

原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/304924.html

四皇后java（四皇后問題圖解）

本文目錄一覽：

八皇后問題的java代碼。

用VB的窮舉法解決四皇后問題，急！

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

9.2 回溯演算法的例子

C語言四皇后問題

Java編程八皇后，但是第一個皇后是我們手動輸入的該怎麼編呢

相關推薦

發表回復