卡在数独作业的回溯步骤上

Question

我是 java 的新手（特别是回溯法），我已经做了将近两天的递归数独求解器，但没有成功。我认为我的回溯步骤是错误的，但我真的不知道如何解决。输入是包含数字和字符“.”的 .txt。代表程序需要完成的地方。（p.s：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定义如下link： 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 以查看您是否从其他地方复制了代码。所以你最好盯着这个解决方案，试着找出你的解决方案哪里出了问题，然后自己尝试纠正这些部分。

卡在数独作业的回溯步骤上

Stuck on Backtracking step on a Sudoku Homework

java

recursion

backtracking