4
\$\begingroup\$

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;
    }
}
\$\endgroup\$

migrated from stackoverflow.com Dec 10 '11 at 20:14

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ you don't need to use this unless your global variable name conflicts with a local one from a parameter. It just looks messy and doesn't do anything. \$\endgroup\$ – Jon Dec 10 '11 at 2:48
  • \$\begingroup\$ Have you identified the parts that take the longest yet? Something as simple as wrapping your methods with System.currentTimeMillis() might get you headed in the right direction. \$\endgroup\$ – Jason Braucht Dec 10 '11 at 2:53
  • \$\begingroup\$ Do you know if your algorithm can realistically be applied to a large grid? Do you know how the computational cost scales with the grid size? Maybe it's not your implementation that is deficient, but the algorithm. \$\endgroup\$ – toto2 Dec 10 '11 at 3:22
  • \$\begingroup\$ Avoid the sqrt as they are quite expensive. You can probably precompute them in a small array. \$\endgroup\$ – toto2 Dec 10 '11 at 3:25
  • \$\begingroup\$ Another microoptimisation: use ints instead of Strings to represent field values, with 0 or a negative number for "missing". You have a lot of string comparisons in inner loops in any sudoku solver, this should shave off some time. \$\endgroup\$ – Inerdial Dec 10 '11 at 4:01
8
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ I've written a Sudoku solver just for fun. I went through all the same issues the OP is having and this answer accurately describes steps I took to make things better. Pencil Marks, Naked Singles, Hidden Singles. When 'guessing' and backtracking are necessary always start with the square with the fewest possibilities and go from there. Nice answer Inerdial! \$\endgroup\$ – kasdega Dec 10 '11 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.