patternjavaMinor
Sudoku solutions finder using brute force and backtracking
Viewed 0 times
forceandfindersolutionsusingbrutesudokubacktracking
Problem
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.
The function
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?
protected void calculateSolutions(final SudokuBoard input) {
if (input.getFilledCells() == 81) {
addSolution(input);
return;
}
for (int grid = 0; grid 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?
Solution
Instead of using a fixed order of filling in cells you can first take the cells with the least amount of options left.
In other words if you know that cell 5,8 can only contain 5 and 6 then try each of them now and reduce the possibilities of the other cells instead of having to come back millions of times just to find out that the cell can't be filled any more.
This requires that you track the number of options in the board.
With a bitset it's doable, though un-setting a square is harder because you need to readjust all affected squares.
Then the algorithm looks something like:
This will still create a lot of new partially solved boards but if you add a
In other words if you know that cell 5,8 can only contain 5 and 6 then try each of them now and reduce the possibilities of the other cells instead of having to come back millions of times just to find out that the cell can't be filled any more.
This requires that you track the number of options in the board.
With a bitset it's doable, though un-setting a square is harder because you need to readjust all affected squares.
class SudokuBoard implements Cloanable{
private Map grid = new HashMap();
//fill in constructor
public void setValue(Position pos, int number){
number = number - 1;//bits are index 0 based
BitSet square = grid.get(pos);
if(!square.get(number))
throw new IllegalArgumentException("number " + number + " can't be set at position " + pos);
square.clear();
square.set(number);
// for each square in the row, collumn and big square do
// square.set(number, false);
}
public Position getSquareWithLeastNumberOfOptions(){
Position result = null;
int count = 10;
for(Map.Entry e : grid.entrySet()){
if(e.getValue().cardinality() e : grid.entrySet()){
if(e.getValue().cardinality() != 1){
return false;
}
}
return true;
}
public boolean isSolvable(){
for(Map.Entry e : grid.entrySet()){
if(e.getValue().cardinality() == 0){
return false;
}
}
return true;
}
@Override
public SudokuBoard clone(){
try{
SudokuBoard clone = (SudokuBoard)super.clone();
clone.grid = new HashMap(grid);
for(Map.Entry e : clone.grid.entrySet()){
e.setValue((BitSet)e.clone());
}
return clone;
} catch(CloneNotSupportedException e){
return null;//can't happen
}
}
}Then the algorithm looks something like:
public Set getAllSolutions(SudokuBoard board){
if(board.isSolved)
return Collections.singleton(board);
if(!board.isSolvable())
return Collections.emptySet();
Set result = new HashSet();
Position pos = board.getSquareWithLeastNumberOfOptions();
for(int num = board.getFirstPossibleNumber(pos); num != 0; num = getNextPossibleNumber(pos, num)){
SudokuBoard newBoard = board.clone();
newboard.setValue(pos, num);
result.addAll(getAllSolutions(newBoard));
}
return result;
}This will still create a lot of new partially solved boards but if you add a
unSetValue(Position) to SudokuBoard then you can reuse the original board and only need to clone it when returning it in the singleton: return Collections.singleton(board.clone());.Code Snippets
class SudokuBoard implements Cloanable{
private Map<Position, BitSet> grid = new HashMap<Position, BitSet>();
//fill in constructor
public void setValue(Position pos, int number){
number = number - 1;//bits are index 0 based
BitSet square = grid.get(pos);
if(!square.get(number))
throw new IllegalArgumentException("number " + number + " can't be set at position " + pos);
square.clear();
square.set(number);
// for each square in the row, collumn and big square do
// square.set(number, false);
}
public Position getSquareWithLeastNumberOfOptions(){
Position result = null;
int count = 10;
for(Map.Entry<Position, BitSet> e : grid.entrySet()){
if(e.getValue().cardinality() < count && e.getValue().cardinality() != 1){
result = e.getKey();
count = e.getValue().cardinality();
}
}
return result;
}
public int getFirstPossibleNumber(Position pos){
return grid.get(pos).getNextSetBit(0)+1;
}
//returns 0 when no more options
public int getNextPossibleNumber(Position pos, int previous){
return grid.get(pos).getNextSetBit(previous)+1;
}
public boolean isSolved(){
for(Map.Entry<Position, BitSet> e : grid.entrySet()){
if(e.getValue().cardinality() != 1){
return false;
}
}
return true;
}
public boolean isSolvable(){
for(Map.Entry<Position, BitSet> e : grid.entrySet()){
if(e.getValue().cardinality() == 0){
return false;
}
}
return true;
}
@Override
public SudokuBoard clone(){
try{
SudokuBoard clone = (SudokuBoard)super.clone();
clone.grid = new HashMap(grid);
for(Map.Entry<Position, BitSet> e : clone.grid.entrySet()){
e.setValue((BitSet)e.clone());
}
return clone;
} catch(CloneNotSupportedException e){
return null;//can't happen
}
}
}public Set<SudokuBoard> getAllSolutions(SudokuBoard board){
if(board.isSolved)
return Collections.singleton(board);
if(!board.isSolvable())
return Collections.emptySet();
Set<SudokuBoard> result = new HashSet<SudokuBoard>();
Position pos = board.getSquareWithLeastNumberOfOptions();
for(int num = board.getFirstPossibleNumber(pos); num != 0; num = getNextPossibleNumber(pos, num)){
SudokuBoard newBoard = board.clone();
newboard.setValue(pos, num);
result.addAll(getAllSolutions(newBoard));
}
return result;
}Context
StackExchange Code Review Q#106220, answer score: 6
Revisions (0)
No revisions yet.