I'm calculating all possible solutions for a given Sudoku board with at least 17 values. My approach is a basic backtracking approach and it works.
protected void calculateSolutions(final SudokuBoard input) {
if (input.getFilledCells() == 81) {
addSolution(input);
return;
}
for (int grid = 0; grid < 9; grid++) {
for (int pos = 0; pos < 9; pos++) {
if (input.getValue(new Position(grid, pos)).isEmpty()) {
for (int number = 1; number <= 9; number++) {
if (isPossibleAtPosition(grid, pos, number)) {
SudokuBoard newInput = input.clone();
newInput.setValue(new Position(grid, pos), new Value(number));
List<SudokuBoard> results = new SudokuBacktrackSolver().solve(newInput);
for (SudokuBoard result : results) {
addSolution(result);
}
}
}
return;
}
}
}
}
The function isPossibleAtPosition
checks whether the number exists in the cell, row or grid. If it is possible, I create a new SudokuBoard
, which ends up in a tree structure, where each solution has a depth of 81.
I also thought about creating a matrix containing all possibilities. This would improve the chance of finding a solution fastest but would produce a big overhead, and as I want to find all possible solutions, it would not be an improvement.
Are there any delimitations to improve the algorithm?
SudokuBacktrackSolver.solve()
method and this function? Why are they split up? \$\endgroup\$