# Sudoku Solver Optimization

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


## migrated from stackoverflow.comDec 10 '11 at 20:14

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

• 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. – Jon Dec 10 '11 at 2:48
• 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. – Jason Braucht Dec 10 '11 at 2:53
• 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 Dec 10 '11 at 3:22
• Avoid the sqrt as they are quite expensive. You can probably precompute them in a small array. – toto2 Dec 10 '11 at 3:25
• 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. – Inerdial Dec 10 '11 at 4:01

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