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

尝试从 Sudoko 方法返回 true 或 false。

当isAnswer()方法返回true时，打印表格。然后从 Sudoko() 方法返回 true。

现在在 for 循环中，递归调用 Sudoko() 方法，检查它是否返回 true 或 false。如果它返回true，则意味着您的选择是正确的并且它会导致解决方案，您无需执行任何其他操作。如果返回 false，请删除您使用 addToSudoko() 方法设置的数字。将表设置为调用 addToSudoko() 方法之前的样子，然后继续迭代。

如果你的 for 循环循环了 9 次，并且没有一个数字有合适的位置，这意味着如果循环结束，则返回 false。

希望这有帮助