Алгоритм возврата в судоку из-за ошибки - PullRequest
0 голосов
/ 29 апреля 2020

Моя проблема в том, что после первого решения мой метод выдает ошибку ArrayIndexOutOfBoundsException

Это простой алгоритм обратного отслеживания, который проверяет возможные значения для каждой пустой ячейки и рекурсивно вызывает метод для следующих ячеек (судоку)

Это трассировка стека для ошибки:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 9 out of bounds for length 9
    at Sudoku.isSafe(Sudoku.java:20)
    at Sudoku.findSaveValues(Sudoku.java:43)
    at Sudoku.sudokuSolver(Sudoku.java:131)
    at Sudoku.sudokuSolver(Sudoku.java:137)
    at Sudoku.sudokuSolver(Sudoku.java:137
    ...
    at Sudoku.sudokuSolver(Sudoku.java:137)
    at Sudoku.sudokuSolver(Sudoku.java:137)
    at Main.main(Main.java:45)

Вот код:

public class Sudoku {

    private static int leaves = 0, solutionNumber = 1, backtracking = 0;
    private static ArrayList<Integer> saveValues;
    private static final int GRID_SIZE = 9;
    static Long startTime = null;

    public static boolean isSafe(int[][] sudoku, int number, int row, int column) {
        // uniques in row
        for (int i = 0; i < GRID_SIZE; i++)
            if (sudoku[i][column] == number) // <<<--- at Sudoku.isSafe(Sudoku.java:20)
                return false;

        // uniques in column
        for (int i = 0; i < GRID_SIZE; i++)
            if (sudoku[row][i] == number)
                return false;

        // uniques in section
        int rowStart = row - row % 3;
        int columnStart = column - column % 3;
        for (int i = rowStart; i < rowStart + 3; i++)
            for (int j = columnStart; j < columnStart + 3; j++)
                if (sudoku[i][j] == number)
                    return false;

        return true;
    }

    public static void findSaveValues(int[][] sudoku, int row, int column) {
        saveValues = new ArrayList<>();
        // adding save values to list
        for (int n = 1; n <= GRID_SIZE; n++)
            if (isSafe(sudoku, n, row, column)) // <<<--- at Sudoku.findSaveValues(Sudoku.java:43)
                saveValues.add(n);
    }

    public static boolean isFull(int[][] sudoku) {
        for (int r = 0; r < GRID_SIZE; r++)
            for (int c = 0; c < GRID_SIZE; c++)
                if (sudoku[r][c] == 0)
                    return false;
        return true;
    }

    public static void sudokuSolver(int[][] sudoku) {
        int row = 0, column = 0;
        boolean breaking;
        // timestamp of start
        if (startTime == null)
            startTime = System.currentTimeMillis();

        if (isFull(sudoku)) {
            long finishTime = System.currentTimeMillis();
            printSudoku(sudoku);
            // raising solution number to print properly
            solutionNumber++;
            System.out.println("Time to solution: " + (finishTime-startTime) + "ms");
        }

        breaking = false;
        for (row = 0; row < GRID_SIZE; row++) {
            for (column = 0; column < GRID_SIZE; column++)
                if (sudoku[row][column] == 0) {
                    breaking = true;
                    break;
                }
            if (breaking)
                break;
        }

        findSaveValues(sudoku, row, column); // <<<--- at Sudoku.sudokuSolver(Sudoku.java:131)
        // evoking recursion for all save values at this point
        for (int number : saveValues) {
            sudoku[row][column] = number;
            // adding amount of visited leaves
            leaves++;
            sudokuSolver(sudoku); // <<<--- at Sudoku.sudokuSolver(Sudoku.java:137)
        }

        sudoku[row][column] = 0;
        // adding count of backtracking moves
        backtracking++;
    }
}

В основной функции он просто вызывается так: Sudoku.sudokuSolver (matrix); // матрица запускается судоку с пустыми ячейками, которая содержит 0

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...