java实现八皇后算法,八皇后算法实际应用

发布时间：2022-11-23

本文目录一览：

  1. java八皇后问题
  2. java：八皇后问题解题思路
  3. JAVA中八皇后问题算法和流程图。要求用回溯法，求大神解答，在线等如果有代码就完美了
  4. [谁能给我一个JAVA的八皇后的代码(加上详细的注解) 谢谢](#谁能给我一个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中八皇后问题算法和流程图。要求用回溯法，求大神解答，在线等如果有代码就完美了

//--------------------------------------
//利用函数递归，解决八皇后问题
//
// 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;i<QUEEN_NUM;++i)
        for(int j=0;j<QUEEN_NUM;++j)
            if(abs(i-m)==abs(j-n))//对角区域填充
            {
                if(label[i][j]==0)
                    label[i][j]=num;
            }
    int i=0,j=0;
    while(i<QUEEN_NUM)//行填充
    {
        if(label[i][n]==0)
            label[i][n]=num;
        ++i;
    }
    while(j<QUEEN_NUM)//列填充
    {
        if(label[m][j]==0)
            label[m][j]=num;
        ++j;
    }
}
void ClearChessBox(int m,int n,int num)
{
    for(int i=0;i<QUEEN_NUM;++i)
        for(int j=0;j<QUEEN_NUM;++j)
            if(abs(i-m)==abs(j-n) && label[i][j]==num)
                label[i][j]=0;
    int i=0,j=0;
    while(i<QUEEN_NUM)
    {
        if(label[i][n]==num)
            label[i][n]=0;
        ++i;
    }
    while(j<QUEEN_NUM)
    {
        if(label[m][j]==num)
            label[m][j]=0;
        ++j;
    }
}
void AllClear()
{
    for(int i=0;i<QUEEN_NUM;++i)
        for(int j=0;j<QUEEN_NUM;++j)
            label[i][j]=0;
}
void PrintResult()
{
    for(int i=0;i<QUEEN_NUM;++i)
    {
        for(int j=0;j<QUEEN_NUM;++j)
            printf("%d ",label[i][j]);
        printf("\n");
    }
}
bool EightQueen(int n/*皇后个数*/,int c/*已经放置的皇后个数*/)
{
    //static int count=0;
    //小于3x3的棋盘是无解的
    if(n<4)
        return false;
    for(int i=0;i<n;++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; j < 8; 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 (i < 8) { //判断是否放完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; i1 < 8; 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; i < 8; i++) //置所有列为安全
            q.col[i] = true;
        for (int i0 = 0; i0 < 16; i0++) //置所有对角线为安全
            q.diagonal[i0] = q.undiagonal[i0] = true;
        q.solve(1);
    }
}
推荐文章