Моя проблема в том, что после первого решения мой метод выдает ошибку 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