i want to make a sudoku solver

Question

Here is the code:

public class sudoku {
    public static void printSudoku(int sudoku[][]){
        for(int i = 0; i < sudoku.length; i++){
            for(int j = 0; j < sudoku[i].length; j++){
                System.out.print(sudoku[i][j] + " ");
            }
            System.out.println();
        }
    }
    public static void sudokuSolver(int sudoku[][], int i, int j){
        if (i == 8 && j == 8) {
            printSudoku(sudoku);
            return;
        }
        if (j == sudoku[i].length) {
            sudokuSolver(sudoku, i+1, 0);
        }
        for(int n = 1; n <= 9; n++){
            if (isSafe(sudoku, i, j, n)) {
                sudoku[i][j] = n;
            }
            sudokuSolver(sudoku, i, j+1);
        }
    }
    public static boolean isSafe(int sudoku[][], int i, int j, int n){
        //row
        for(int c = 0; c <= 8; c++){
            if (sudoku[i][c] == n) {
                return false;
            }
        }
        //col
        for(int r = 0; r <= 8; r++){
            if (sudoku[r][j] == n) {
                return false;
            }
        }

        //matrix
        int sr = (i/3)*3, sc = (j/3)*3;
        for(int r = sr; r<sr+3;r++){
            for(int c = sc; c < sc+3; c++){
                if (sudoku[r][c]==n) {
                    return false;
                }
            }
        }
        return true;
    }
    public static void main(String[] args) {
        int sudoku[][] = {{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}};
        sudokuSolver(sudoku, 0, 0);
    }
}

I know that we can solve it using backtracking. But whats wrong with this method and i dont know why the stack is getting overflown as i have set the base case as well.

i was expecting a solved sudoky. Instead i am getting "Stack Overflow Error".

Answer 1

There are several issues:

• When the condition j == sudoku[i].length is true, and the recursive call returns, the execution continues with with for loop below, where j+1 is passed to the recursive call, and now the base case will never be reached, as each next recursive call will have a value for j that is one more... indefinitely, until you hit stack overflow. The solution is to add a return right after the call sudokuSolver(sudoku, i+1, 0)

• In the for loop, the recursive call is made unconditionally, so also when the value could not be placed (isSafe returned false). But that means that the corresponding cell is left empty, and eventually the base case will kick in and print a board that is mostly filled with zeroes. Instead, the recursive call should only be made when the value could be placed in the cell -- so place it inside the if isSafe block. Otherwise the for loop should try another value without making a recursive call.

• As you don't apply backtracking, but do continue after coming back from recursion, you have to take into account that the cells that were filled by the deeper recursive calls are still there and the board will only get more values (never less) until it represents a configuration where no more valid cells can be filled in. And then the process will never find a valid Sudoku. The easiest solution to this is to just add one line of code that implements the backtracking, i.e. that sets the current cell back to 0.

Here is your code with corrections for the above. Comments indicate where changes were made:

    public static void printSudoku(int sudoku[][]){
        for(int i = 0; i < sudoku.length; i++){
            for(int j = 0; j < sudoku[i].length; j++){
                System.out.print(sudoku[i][j] + " ");
            }
            System.out.println();
        }
        // For better visual distinction between different Sudokus, 
        //    leave one line empty in the output: 
        System.out.println(); 
    }

    public static void sudokuSolver(int sudoku[][], int i, int j){
        if (i == 8 && j == 8) {
            printSudoku(sudoku);
            return;
        }
        if (j == sudoku[i].length) {
            sudokuSolver(sudoku, i+1, 0);
            // Don't allow execution to continue into the loop below 
            //    with an invalid value for `j`:
            return; 
        }
        for(int n = 1; n <= 9; n++){
            if (isSafe(sudoku, i, j, n)) {
                sudoku[i][j] = n;
                // The recursive call should only be made when we placed a value
                sudokuSolver(sudoku, i, j+1);
                // We must backtrack to have any hope of success:
                sudoku[i][j] = 0;
            }
        }
    }