Sudoku solutions finder using brute force and backtracking 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 &lt; 9; grid++) {
        for (int pos = 0; pos &lt; 9; pos++) {
            if (input.getValue(new Position(grid, pos)).isEmpty()) {
                for (int number = 1; number &lt;= 9; number++) {
                    if (isPossibleAtPosition(grid, pos, number)) {

                        SudokuBoard newInput = input.clone();
                        newInput.setValue(new Position(grid, pos), new Value(number));
                        List&lt;SudokuBoard&gt; 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?
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&lt;Position, BitSet&gt; grid = new HashMap&lt;Position, BitSet&gt;();
    //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&lt;Position, BitSet&gt; e : grid.entrySet()){
            if(e.getValue().cardinality() &lt; count &amp;&amp; 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&lt;Position, BitSet&gt; e : grid.entrySet()){
            if(e.getValue().cardinality() != 1){
                return false;
            }
        }
        return true;
    }


    public boolean isSolvable(){

        for(Map.Entry&lt;Position, BitSet&gt; 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&lt;Position, BitSet&gt; 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&lt;SudokuBoard&gt; getAllSolutions(SudokuBoard board){
    if(board.isSolved)
        return Collections.singleton(board);
    if(!board.isSolvable())
        return Collections.emptySet();

    Set&lt;SudokuBoard&gt; result = new HashSet&lt;SudokuBoard&gt;();

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