Застрял на шаг назад на домашнюю работу судоку

Question

Я совершенно новичок в java (особенно бэктрекинг), и я делаю рекурсивный решатель судоку почти два дня безуспешно. Я думаю, что мой шаг возврата неверен, но я действительно не знаю, как это исправить. Ввод .txt с цифрами и символом "."представляющий, где программа должна выполнить. (ps: 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);
    }
}

I 'm получает нулевой вывод без сообщения об исключении.

вот .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;
}

Прежде чем копировать вставку, имейте в виду, что некоторые преподаватели или профессора также изучают переполнение стека, чтобы узнать, скопировали ли вы код откуда-то еще. Так что, возможно, вам лучше взглянуть на это решение и попытаться выяснить, в чем причина вашего решения, и попытаться исправить эти части самостоятельно.