本文目录一览：
- 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
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,
// 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;
//小于3x3的棋盘是无解的
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);
}
}
