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) {
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++){

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

StackExchange Code Review Q#6701, answer score: 8