java - n 皇后区的输出与预期输出不匹配

Question

我已经实现了 n 皇后问题。但是，与在线解决方案相比，我的组合比实际答案多。

下面是我的代码

public class Queens
{
    static int rows = 5;
    static int cols = 5;

    public static void main(String[] args)
    {
        int[] column = {-1,-1,-1,-1,-1};
        fun(0, column);
    }

    /* j is basically each column */
    static void fun(int j, int[] column)
    {
        if(j == cols)
        {
            System.out.print("success : ");
            for(int k = 0;k<column.length;k++)
            {
                System.out.print(column[k]);
            }
            System.out.println("");
            return;
        }

        /* Each column could have the queen in any of the rows */
        for(int i = 0;i <rows ;i++)
        {

            if(isValid(column,j,i) == 1)
            {
                int[] temp = new int[rows];
                for(int k = 0;k<column.length;k++)
                    temp[k] = column[k];

                column[j] = i;
                fun(j+1,column);

                for(int k = 0;k<temp.length;k++)
                    column[k] = temp[k];
            }
        }
    }

    static int isValid(int[] a, int row, int check)
    {
        int lastindex = 0;

        /* check if they're in the same row */
        for(int i = 0;i<a.length;i++)
        {
            if(a[i] == -1)
            {
                lastindex = i-1;
                break;
            }

            if(a[i] == check)
                return 0;
        }

        /* check if they're in the same diagonal */
        if(lastindex >= 0)
        {
            /* diagonal on the rise */       /* falling diagonal */
            if( (a[lastindex] == check-1) || (a[lastindex] == check+1) )
                return 0;
        }

        /* Note : It can't be in the same column since you're selecting only one for each column, the for loop */

        return 1;
    }
}

这是我对 5-queens 问题的输出。 (在代码中，您可以通过相应地更改行和列的值并更改数组来获得任何 n)

success : 13524
success : 14253
success : 24135
success : 24153 -
success : 25314
success : 31425
success : 31524 -
success : 35142 -
success : 35241
success : 41352
success : 42513 -
success : 42531
success : 52413
success : 53142

但是，末尾标有连字符的那些在 online site 中丢失了我用来比较输出

请告诉我这四个不一致的原因。 (对于 8 皇后，我上面的代码在输出中给出了 5242 种组合，肯定是我在 isValid 函数中做错了什么)

编辑:非常感谢 vish4071，我现在更改了 isValid() 函数并获得了正确的输出；我不知道每一步都必须检查对角线。

代码

public class Queens
{
    static int rows = 8;
    static int cols = 8;

    public static void main(String[] args)
    {
        int[] column = {-1,-1,-1,-1,-1,-1,-1,-1};
        fun(0, column);
    }

    /* j is basically each column */
    static void fun(int j, int[] column)
    {
        if(j == cols)
        {
            System.out.print("success : ");
            for(int k = 0;k<column.length;k++)
            {
                System.out.print(column[k]);
            }
            System.out.println("");
            return;
        }

        /* Each column could have the queen in any of the rows */
        for(int i = 0;i <rows ;i++)
        {

            if(isValid(column,j,i) == 1)
            {
                int[] temp = new int[rows];
                for(int k = 0;k<column.length;k++)
                    temp[k] = column[k];

                column[j] = i;
                fun(j+1,column);

                for(int k = 0;k<temp.length;k++)
                    column[k] = temp[k];
            }
        }
    }

    static int isValid(int[] a, int col, int check)
    {
        for(int i = 0;i<a.length;i++)
        {
            if(a[i] == -1)
                break;

            /* check if they're in the same row */
            if(check == a[i])
                return 0;

            /* check if they're in the same diagonal */
            if( Math.abs(check-a[i]) == (col-i) )
                return 0;
        }

        /* Note : It can't be in the same column since you're selecting only one for each column, the for loop */

        return 1;
    }
}

Answer 1

您对对角线的检查是错误的。不要使用 lastindex。检查 a 中不是 -1 的所有值的相同对角线。

我将使用您的输出之一(您用连字符表示)作为示例进行解释。让我们以 24153 为例。
假设您的 a 现在是 [2,4,1,-1,-1]，即。您现在要填充索引 3。您的最后一个索引将是 1 并且在矩阵中，(2,1) 和 (3,5) 不在同一条对角线上。因此，它接受第 4 个值作为 5 不在同一对角线上，而它与索引 0 处的值在同一对角线上，即。 2，因为 (0,2) 和 (3,5) 位于同一条对角线上。因此，检查所有值。