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 anyone could take a look at my code and give me some ideas on how to optimize it.

My Code:

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

Thanks!