Sudoku solutions finder using brute force and backtracking
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());.