Sudoku Solver Optimization

Question

I am currently working on a Sudoku solver that should be able to solve a 25 x 25 grid. However, I am experiencing problems optimizing it to run quick enough to actually get a result with any grid bigger than 9 x 9. I was wondering if anyone could take a look at my code and give me some ideas on how to optimize it.

public class SudokuGrid {
    private String[][] grid;

    /**
     * Constructs an empty 9x9 Sudoku Grid.
     */
    public SudokuGrid() {
        this(16);
    }

    /**
     * Constructs an empty, square Sudoku grid.
     * @param boardSize the length of each row & column
     */
    public SudokuGrid(int gridSize) {
        this.grid = new String[gridSize][gridSize];
        for (int r = 0; r < this.grid.length; r++) {
            for (int c = 0; c < this.grid.length; c++) {
                this.grid[r][c] = "-";
            }
        }
    }

    /**
     * Constructs a partially filled Sudoku grid.
     * @param str the contents of the grid (using '-' for blank)
     */
    public SudokuGrid(String str) {
        String[] contents = str.split("\\s+");
        int gridSize = (int)Math.sqrt(contents.length);

        this.grid = new String[gridSize][gridSize];
        for (int i = 0; i < contents.length; i++) {
            this.grid[i/gridSize][i%gridSize] = contents[i];
        }
    }

    /**
     * Fills the Sudoku grid with numbers using recursive backtracking.
     * @return whether the grid was successfully filled
     */

    public boolean fillGrid(){
        return fillGrid(0,0);
    }

    private boolean fillGrid(int row, int col){
        if (col >= this.grid.length) {
            col = 0;
            if (++row >= this.grid.length)
                return true;
        }
        if (!this.grid[row][col].equals("-")){
            return fillGrid(row , col + 1);
        }
        for (int i = 1; i <= this.grid.length; i++) {
            String temp = ""+i;
            if (isValidValue(row, col, temp)) {
                this.grid[row][col] = temp;
                if (fillGrid(row, col + 1)){
                    return true;
                }
            }
        }
        grid[row][col] = "-";
        return false;
    }


    private boolean isValidValue(int row, int col, String val) {
        for (int i = 0; i < this.grid.length; i++){
            if (val.equals(this.grid[i][col])){
                return false;
            }
        }

        for (int j = 0; j < this.grid.length; j++){
            if (val.equals(this.grid[row][j])){
                return false;
            }
        }

        double squareRootVal = Math.sqrt(this.grid.length);
        int rowOffset = (row / (int)squareRootVal) * (int)squareRootVal;
        int colOffset = (col / (int)squareRootVal) * (int)squareRootVal;
        for (int i = 0; i < squareRootVal; i++) {
            for (int j = 0; j < squareRootVal; j++){
                if (val.equals(this.grid[rowOffset + i][colOffset + j])){
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Constructs a String representation of the grid.
     * @return the grid in a displayable row/column format
     */
    @Override
    public String toString() {
        String output = "";
        for (int r = 0; r < this.grid.length; r++) {
            for (int c = 0; c < this.grid.length; c++) {
                output += grid[r][c] + " ";
            }
            if (r < this.grid.length-1) {
                output += "\n";
            }
        }
        return output;
    }
}

Answer 1

isValidValue() is needlessly simple – you check all 9 values for every field always. Instead, try implementing "pencil marks" that humans use when solving sudoku. For every field without a value, you should explicitly store which values can still be entered into this field. (In say a boolean[rows][cols][value]).

Then, when you place a number, remove it as a candidate value from other fields in the row/col/box, and add it again as you backtrack out of that try.

Other techniques humans use can also be implemented in software. Once you track pencil marks, Hidden Single should be fairly straightforward. (In fact it might be better to try that one before a backtracking search.) You could also try to speed up the search by filling in squares with the fewest possible candidates first, and by trying the digits you've already placed the most first. (I'm less certain that these will help a software solver, but they might reach a conflict that will cause a backtrack earlier.)