weixin_44905661
ZHANG H.
2019-10-30 18:15
采纳率: 100%
浏览 234
已采纳

这个算法的问题在哪里?

这是八皇后问题的算法,来源于一本书的习题的答案,源码是C++并且是一个函数,不是完整的程序,我把它改写成了Java,运行了一下,发现运行结果的每个方案的第一个元素只有(1,1),也就是第一个皇后的位置都是最左上角。代码中的主函数是我自己写的,并且包含“//”的注释都是我自己的理解,原来都是没有的。请各位大神看一下是算法本身的问题还是主函数调用的问题?

public class Test 
{
    /**
     * 算法思路:假设前i-1行的皇后已经安放成功,现在要在第i行的
     * 适当列安放皇后,使得它与前i-1行安放的皇后在行方向、列方向
     * 和斜线方向都不冲突。为此,试探第i行的所有8个位置(列),
     * 如果某一列能够安放皇后,就可以递归到第i+1行继续寻找下一行
     * 皇后可安放的位置。为了记录各行皇后安放的位置,设置一个
     * 一维数组g[8],在g[i]中记录了该行皇后安放在第几列。
     */
    public static void Queen(int[] g,int i)
    {
        int j,k,conflict;//j是列,k是行,conflict表示位置是否冲突,1为真,0为假
        if(i==8)//单个方案寻找完毕,输出之
        {
            for(int m=0;m<8;m++)
                System.out.print("("+(m+1)+","+(g[m]+1)+") ");
            System.out.println(";");
            System.out.println();
            return;
        }
        else
        {
            for(j=0;j<8;j++)
            {
                conflict=0;
                //对于每一列,从第1行开始扫描直到第i行,
                //j==g[k]表示同一列,i-k==j-g[k]或者k-i==g[k]-j表示同一斜线
                for(k=0;k<i;k++)
                    if(j==g[k]||i-k==j-g[k]||k-i==g[k]-j)
                        conflict=1;
                if(conflict==0)
                {
                    g[i]=j;
                    Queen(g,i+1);
                }
            }
        }
    }
    public static void main(String[] args) 
    {
        int[] g=new int[8];
        System.out.println("所有方案皇后坐标如下:");
        Queen(g,1);//假设第1行已放置皇后
    }
}

原来的答案(c++源码)如下:
图片说明

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • caozhy
    已采纳

    原来的程序怎么写的,是否正确。
    public static void Queen(int[] g,int i)
    你这样写,g是传引用,也就是所有的递归调用,g都是修改的同一个

    点赞 评论

相关推荐