「java八皇后算法」java八皇后问题
今天给各位分享java八皇后算法的知识，其中也会对java八皇后问题进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
Java 八皇后问题解释
public class Queen{//同栏是否有皇后，1表示有private int[] column;//右上至左下是否有皇后private int[] rup;//左上至右下是否有皇后private int[] lup;//解答private int[] queen;//解答编号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; //初始定义全部无皇后 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)){//若无皇后queen[i]=j;//设定为占用column[j]=rup[i+j]=lup[i-j+8]=1;backtrack(i+1); //循环调用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);}}
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中八皇后问题算法和流程图。要求用回溯法，求大神解答，在线等如果有代码就完美了
[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;
}
八皇后问题算法详解
八皇后问题，是一个古老而著名的问题，是 回溯算法 的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯 认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。
本文的主要描述的是基于回溯算法思想的求解算法，并尽可能在细节上给予读者直观展示，以使得读者可以有更好的理解。抛砖引玉，如有错误请不吝赐教。
算法的关键在于用一个二维数组chess [ ] [ ] 来记录每一个位置(第 i 行第 j 列)是否合法（行列对角线上没有填皇后，对应于数组 chess [ i ] [ j ] 为 0），用一个一维数Queenplace [ ] 组来记录每一行上皇后的列标（比如Queenplace [ row ] =column 表示第 row 行第 column 列填入皇后）。
行数 i 从第一行开始，遍历每一列 j ，如果chess [ i ] [ j ] 为0，那么说明此位置可以填入皇后，则将chess中与此位置同行同列同对角线的value自增 1 并且在 数组Queenplace 中记录相应的坐标。然后递归计算每一行直到最后一行成功填入皇后并在此时打印棋盘 。最后进行回溯，恢复chess [ ] [ ] ，将chess中与此位置同行同列同对角线的value自减 1 并继续进行下一列的计算。
java八皇后算法的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于java八皇后问题、java八皇后算法的信息别忘了在本站进行查找喔。
发布于：2022-12-15，除非注明，否则均为原创文章，转载请注明出处。