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

• Jon: 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.
• Jason Braucht: 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.
• toto2: 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.
• toto2: Avoid the sqrt as they are quite expensive. You can probably precompute them in a small array.
• Inerdial: 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.

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

• kasdega: 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!