坚持数独作业的回溯步骤

Question

我对java很陌生（特别是回溯），并且我正在进行递归数独求解器近两天而没有成功。我认为我的回溯步骤是错误的，但是我真的不知道如何解决。输入是带有数字和字符“。”的.txt。表示程序需要在哪里执行。 （注：Std.In是我老师的教科书提供的一个库，它读取.txt并将其转换为半板数组。）

我知道问题不在原路（检查数独规则是否已分配该数字的人）和相关功能。

StdIn库可以在以下网站下载：https://introcs.cs.princeton.edu/java/stdlib/

public class Sudoku {
    private static void Solve(int[] board) {
        SolveCell(board, 0);
    }

    private static void SolveCell(int[] board, int cell) {
        if (cell == 81) {
            show(board);
            return;
        }
        if (board[cell] != 0) {
            SolveCell(board, cell + 1);
            return;
        }
        for (int n = 1; n <= 9; n++) {
            if (!backtrack(board, cell, n)) {
                board[cell] = n;
                SolveCell(board, cell + 1);
            }
        }
        board[cell] = 0;
    }

    private static void show(int[] board) {
        for (int i = 0; i < 81; i++) {
            if ((i + 1) % 9 == 0) {
                System.out.println(board[i]);
            } else {
                System.out.print(board[i]);
                System.out.print(" ");
            }
        }
    }

    private static int choose1(int cell) {
        int l = 0;
        for (int i = 0; i <= 8; i++) {
            if (cell > i * 9 - 1 && cell < (i + 1) * 9 - 1) {
                l = i * 9;
            }
        }
        return l;
    }

    private static int choose2(int cell) {
        int l = 0;
        for (int i = 0; i <= 8; i++) {
            if (cell + i % 9 == 0) {
                l = i;
                return l;
            }
        }
        return l;
    }

    private static int choose3(int cell) {
        int l = 0;
        for (int i = 0; i <= 9; i += 3) {
            for (int j = 0; j <= 81; j += 27) {
                if ((cell % 9 > i && cell % 9 < i + 3) && (cell > j && cell < j + 27)) {
                    l = i + j;
                    return l;
                }
            }
        }
        return l;
    }

    private static boolean backtrack(int[] board, int cell, int n) {
        int linechecker = choose1(cell);
        for (int i = 0; i < 9; i++) {
            if (board[linechecker + i] == n && linechecker + i != cell) {
                return true;
            }
        }
        int columnchecker = choose2(cell);
        for (int i = 0; i < 9; i++) {
            if (board[columnchecker + 9 * i] == n && columnchecker + 9 * i != cell) {
                return true;
            }
        }
        int squarechecker = choose3(cell);
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 27; j += 9) {
                if (board[squarechecker + i + j] == n && squarechecker + i + j != cell) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] board = new int[81];
        String[] semiboard = new String[81];
        for (int i = 0; i < 81; i++) {
            semiboard[i] = StdIn.readString();
            if (semiboard[i].matches("\\d")) {
                board[i] = Integer.parseInt(semiboard[i]);
            } else {
                board[i] = 0;
            }
        }

        Solve(board);
    }
}

我收到没有异常消息的空输出。

这里是.txt：

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

StdIn.readString在以下链接中定义：https://introcs.cs.princeton.edu/java/stdlib/StdIn.java.html

Answer 1

您从未达到条件cell == 81为真的状态。我没有进行调试以确切地说出原因是什么。

基本上是您的backtrack方法错误。这是现在的样子：

    private static boolean backtrack(int[] board, int cell, int value) {
    int line = cell / 9;
    //check line
    for (int i = 0; i < 9; i++) {
        if ((board[line * 9 + i] == value)) {
            return true;
        }
    }

    int column = cell % 9;
    //check column
    for (int i = 0; i < 9; i++) {
        if (board[column + i * 9] == value) {
            return true;
        }
    }

    int squareLine = line - (line % 3);
    int squareColumn = column - (column % 3);
    //check square
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[(squareLine + i) * 9 + (squareColumn + j)] == value) {
                return true;
            }
        }
    }

    return false;
}

在复制粘贴之前，请注意，有些老师或教授也会调查Stack Overflow，以查看是否从其他地方复制了代码。因此，您最好盯着此解决方案，并尝试找出解决方案出了哪些问题，然后尝试自己更正这些部分。