Sudoku solutions finder using brute force and backtracking

Question

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?

Answer 1

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.

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
        }
    }

}

Then the algorithm looks something like:

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;
}

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());.

Answer 2

creating a lot of objects

You are creating a new object every time you branch:

List<SudokuBoard> results = new SudokuBacktrackSolver().solve(newInput);

With a small modification you can use the same object and avoid a lot of heap allocations.

Here is some pseudo-code:

List<SudokuBoard> solve(SudokuBoard input) {
  List<SudokuBoard> results;

  if no empty cells:
    return input as a List<SudokuBoard>

  for all (grid,pos):
    if input[grid,pos] is empty:
      for digit in 1..9:
        if digit is possible at (grid,pos):
          newInput = input with digit at (grid,pos)
          newResults = solve(newInput)
          append newResults to results;
      return
}

avoid re-copying solutions

If you think about how the search proceeds you'll see that you are re-copying the solutions from the child branch to the parent branch.

You can avoid creating all of these extra lists by just appending to single results list.

A new version of solve implementing this idea:

// an instance member of the solver object:
List<SudokuBoard> results;

void solve(SudokuBoard input) {
  List<SudokuBoard> results;

  if no empty cells:
    append input to this.results

  for all (grid,pos):
    if (grid,pos) is empty:
      for digit in 1..9:
        if digit is possible at (grid,pos):
          newInput = input with digit at (grid,pos)
          solve(newInput)
      return
}

avoid testing already filled cells

You are visiting the cells in this order:

(0,0) - (0,1) - (0,2) - ... (0,9) - (1,0) - ...

When branching on a cell all of the cells before it are guaranteed to have assignments. Therefore you can abbreviate your search for the next empty cell by passing in the cell number you are branching on.

void solve(SudokuBoard input, int startingAt) {

  // find next empty cell after startingAt
  while (startingAt < 81) {
    if cell (startingAt / 9, startingAt % 9) is empty:
      break
    startingAt++
  }

  if startingAt >= 81:
    append input to this.results
  else:
    x, y = startingAt / 9, startingAt % 9
    for digit in 1..9:
      if digit is possible at (x,y):
        newInput = input with digit at (x,y)
        solve(newInput, startingAt+1)
}

avoid creating a new board

Finally, you don't even have to create a new SudokuBoard when you branch. Just reuse the existing one:

// instance members:
List<SudokuBoard> results;
SudokuBoard input;

void solve(int startingAt) {
  // advance startingAt to the next empty cell
  ...

  if startingAt >= 81:
    append a copy of this.input to this.results
  else:
    x, y = startingAt / 9, startingAt % 9
    for digit in 1..9:
      if digit is possible at (x,y):
        this.input[x][y] = digit
        solve(startingAt+1)
}

The only caveat is that you have to make a copy of the board when you add it to the results list.