Java 数独求解器回溯

Question

我正在尝试构建数独解算器。我知道我的代码很乱，可能会有更简单的方法来完成它，但我想按照我开始的方式完成算法。

算法开始做我想做的事情（用第一个适合的数字填充空白），但是当它到达一个没有选项的点时，我不知道如何返回并删除最后一个数字我插入以尝试另一种组合。但我不能只从矩阵中删除最后一个数字，因为它可能是算法未放置的数字。

如果有人能提供帮助，我将不胜感激。

public class Backtracking{

public static void Sudoku(int[][] sudokuTable){
    if (isAnswer(sudokuTable)){
        printSudoku(sudokuTable);
    }else{
        for (int j = 1; j <=9; j++){
            if (canfit(sudokuTable, j)){
                addToSudoku(sudokuTable, j);
                printSudoku(sudokuTable);
                Sudoku(sudokuTable);
            }
        }
    }
}

public static void addToSudoku(int[][] sudokuTable, int n){
    int i = 0;
    int j = 0;
    boolean done = false;
    while (i < 9 && !done){
        while (j < 9 && !done){
            if (sudokuTable[i][j] == 0){
                sudokuTable[i][j] = n;
                done = true;
            }
            j++;
        }
        i++;
    }
}

public static void printSudoku(int[][] sudokuTable){
    for (int i = 0; i < 9; i++){
        for (int j = 0; j < 9; j++){
            System.out.print(sudokuTable[i][j] + " ");
        }
        System.out.println();
    }
    System.out.println();
}

public static boolean isAnswer(int[][] sudokuTable){
    int sum = 0;
    for (int i = 0; i < 9; i++){
        for (int j = 0 ; j < 9; j++){
            if (sudokuTable[i][j] > 9 || sudokuTable[i][j] < 1)
                return false;
            else
                sum++;
        }
    }
    if (sum != 405)
        return false;
    return true;
}

public static boolean canfit(int[][] sudokuTable, int n){
    int i = 0;
    int j = 0;
    boolean pos = false;
    boolean fit = true;
    while (i < 9 && !pos){
        while (j < 9 && !pos){
            if (sudokuTable[i][j] == 0)
                pos = true;
            else
                j++;
        }
        if (!pos)
            i++;
    }
    for (int k = 0; k < 9; k++){
        if (sudokuTable[i][k] == n && k != j)
            fit = false;
    }
    if (fit){
        for (int l = 0; l < 9; l++){
            if(sudokuTable[l][j] == n && l != i)
                fit = false;
        }
    }
    if (fit){
        if (i >= 0 && i < 3)
            i = 0;
        else if (i >=3 && i < 6)
            i = 3;
        else if (i >=6 && i < 9)
            i = 6;
        if (j >= 0 && j < 3)
            j = 0;
        else if (j >=3 && j < 6)
            j = 3;
        else if (j >=6 && j < 9)
            j = 6;
        for (int m = i; m < i+3; m++){
            for (int o = j; o < j+3; o++){
                if (sudokuTable[m][o] == n)
                    fit = false;
            }
        }
    }
    return fit;
}

Answer 1

尝试用你的数独方法 return 判断真假。

当isAnswer()方法returns true时，打印table。然后 return true 来自 Sudoko() 方法。

现在在您的 for 循环中，递归调用 Sudoko() 方法，检查它是 return 还是 true 或 false。如果是returns true，那就说明你的选择是正确的，并且有解决办法，你不需要做任何其他事情。如果它 returns false，删除您使用 addToSudoko() 方法设置的数字。使 table 保持调用 addToSudoko() 方法之前的状态并继续迭代。

如果你的for循环，循环了9次并且none的数字有一个suitable点，这意味着如果循环结束，return false.

希望对您有所帮助

Answer 2

实际上你可以使用数组回溯走法，每次走法错误你只是开始删除一些走法并尝试不同的走法，但是这有一个问题：

尝试所有可能的走法的复杂性是巨大的（尝试一个 81 位数字的所有数字需要多长时间？即使你在这里和那里减少计算时间，你将需要宇宙中所有的时间)
数独的主要问题是，如果您随机移动，您不知道哪一步是错误的。

假设以下案例 sudoky 具有 2x2 个单元格：

+----+----++-----+-----+
| 1  |  2 ||  3  |  4  |
+----+----++-----+-----+
| 4  |  3 ||  1  |  2  |
+====+====++=====+=====+
| 2  |  1 ||  4  |  3  |
+----+----++-----+-----+
| 3  |  4 ||  2  |  1  |
+----+----++-----+-----+

如果您在以下（未解决的）情况下使用您的算法：

+----+----++-----+-----+
| 1  |    ||     |  4  |
+----+----++-----+-----+
|    |    ||     |     |
+====+====++=====+=====+
| 2  |    ||     |     |
+----+----++-----+-----+
|    |  4 ||     |  1  |
+----+----++-----+-----+

有可能他会运行变成下面的顺序

+----+----++-----+-----+
| 1  |    ||  2  |  4  |
+----+----++-----+-----+
|    |    ||  2  |     |
+====+====++=====+=====+
| 2  |    ||     |     |
+----+----++-----+-----+
|    |  4 ||     |  1  |
+----+----++-----+-----+

实际上添加的"twos"都是错误的，但是当你的算法发现那些是错误的，因为你在同一列中有2个"twos"，你不知道哪一个是错误的（第一个添加的，第二个添加的，还是两者都有？）

一个正确的回溯算法应该是这样的：

您从 81 个元胞数组开始，然后开始放置数字（按顺序）。

.

 for(int i=0; i<81; i++)
    array[i] = TryNumber();

.

然后你检查每个添加的数字是否正确。

.

if(SomeNumberNotCorrect())
    break;  // you know you can stop "tryingnumbers" so you can save on loop executions

.

但你不知道哪个是错误的号码

现在编写一个正确的算法来通过尝试解决数独问题而不是运行数百万年是相当长的时间，我不能在这里写，但我认为你选择的方式不是最好的。最好的方法是应用玩家使用的相同策略。请记住，如果您想要一种算法以类似于计算机下国际象棋的方式解决数独问题，您的算法将需要比国际象棋游戏更多的时间（事实上，计算机无法分析国际象棋移动超过 5-6 回合） .但实际上数独可以用更快的算法来解决。

相反，我过去已经完成了一个简单的求解器，您实际上可以尝试应用玩家用来求解它的相同策略：

例如：

对于每个单元格，检查当前的扇区、列和行是否已经有除 1 以外的所有数字，然后您可以添加该数字。并检查每个单元格是否只需要 81*81*81 次移动。

当你的解算器在数独上找不到更多解法时，这只是因为你必须作为玩家开发一个新的策略，然后你需要将它应用到你的程序中，简而言之，你将有一个程序可以能够解决每个数独（不是很难，实际上这就是那里有很多免费数独求解器的原因）。

Java 数独求解器回溯

Java Sudoku solver backtracking

java

solver

sudoku

backtracking