本文目录一览:
- 1、java八皇后问题
- 2、java:八皇后问题解题思路
- 3、JAVA中八皇后问题算法和流程图。要求用回溯法,求大神解答,在线等如果有代码就完美了
- 4、谁能给我一个JAVA的八皇后的代码(加上详细的注解) 谢谢
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:八皇后问题解题思路
递归:
首先每一行放置均会循环,也就是每一行的皇后都会被依次放置在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中八皇后问题算法和流程图。要求用回溯法,求大神解答,在线等如果有代码就完美了
[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;
}
谁能给我一个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;j8;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(i8) //判断是否放完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;i18;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;i8;i++) //置所有列为安全
q.col[i]=true;
for(int i0=0;i016;i0++) //置所有对角线为安全
q.diagonal[i0]=q.undiagonal[i0]=true;
q.solve(1);
}
}