为什么我的 JAVA 使用回溯法解决数独问题的代码没有给出任何解决方案？

Question

这是 JAVA 中的代码，用于使用回溯解决任何 9*9 数独网格的数独问题。它不打印任何输出。我找不到这个错误。请帮忙。我以 9*9 网格的形式将其中一个示例输入 int 包含在主函数中。 is_safe 函数如果通过检查同一行、同一列和相应的 3*3 网格将所选字符放在那里是安全的。基本情况在 cr 变为 9 时检查，即到达板的末端，而 cl 变为 0，即我们到达板外时。那么可能已经找到了可能的解决方案。我们在那个时候打印电路板并 return 到调用函数。逻辑上似乎是正确的，但它没有打印任何输出。

    public static boolean is_safe(int mat[][],int cr,int cl,int i)
    {
        for(int k=0;k<mat.length;k++)
        {
            if(k!=cl&&mat[cr][k]==i)
            return false;
            if(k!=cr&&mat[k][cl]==i)
            return false;
        }
        int row=cr-cr%3;
        int col=cl-cl%3;
        for(int k=0;k<3;k++)
        {
            for(int l=0;l<3;l++)
            {
                if(mat[k+row][l+col]==i)
                return false;
            }
        }
        return true;
    }
    public static void print(int mat[][])
    {
        for(int i=0;i<mat.length;i++)
        {
            for(int j=0;j<mat[0].length;j++)
            {
                System.out.println(mat[i][j]);
            }
            System.out.println();
        }
    }
    public static void func(int mat[][],int cr,int cl)
    {
        if(cr==mat.length&&cl==0)
        {
            print(mat);
            return;
        }
        int i=cr,j=cl;
        if(mat[cr][cl]!=0)
        {
            if(cl+1==9)
            func(mat,cr+1,0);
            else
            func(mat,cr,cl+1);
        }
        else{
        for(int k=1;k<=9;k++)
        {
            if(is_safe(mat,i,j,k))
            {
                mat[i][j]=k;
                if(j+1==mat.length)
                func(mat,i+1,0);
                else
                func(mat, i, j+1);
                mat[i][j]=0;
            }
        }
    }
    }
    public static void main(String[] args) {
        int mat[][]={{3,0,6,5,0,8,4,0,0},
                     {5,2,0,0,0,0,0,0,0},
                     {0,8,7,0,0,0,0,3,1},
                     {0,0,3,0,1,0,0,8,0},
                     {9,0,0,8,6,3,0,1,5},
                     {0,5,0,0,9,0,6,0,0},
                     {1,3,0,0,0,0,2,5,0},
                     {0,0,0,0,0,0,0,7,4},
                     {0,0,5,2,0,6,3,0,0}};
        func(mat,0,0);
    }
}```

Answer 1

您的打印方法从未被调用！看来数独无解了！

通过以下输入，您的代码可以正常工作：

{{3,0,6,5,0,8,4,0,0},
{5,2,0,0,0,0,0,0,0},
{0,8,7,0,0,0,0,3,1},
{0,0,3,0,1,0,0,8,0},
{9,0,0,8,6,3,0,0,5},
{0,5,0,0,9,0,6,0,0},
{1,3,0,0,0,0,2,5,0},
{0,0,0,0,0,0,0,7,4},
{0,0,5,2,0,6,3,0,0}};

您还可以更改打印方法以使其更具可读性：

public static void print(int mat[][]) {
    for (int i = 0; i < mat.length; i++) {
        List<String> stringList = Arrays.stream(mat[i])
                .mapToObj(String::valueOf).collect(Collectors.toList());
        System.out.println(String.join(" ", stringList));
    }
}

输出：

3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9

为什么我的 JAVA 使用回溯法解决数独问题的代码没有给出任何解决方案？

Why is my JAVA code for solving sudoku using backtracking not giving any solution?

java

sudoku

backtracking