Sudoku Solver Recursion

Question

I encountered this problem while solving a leetcode problem (https://leetcode.com/problems/sudoku-solver/).

The problem states like that:

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

My solution is

public class Solution {
    public void solveSudoku(char[][] board) {
        helper(board, 0, 0);
    }   


    //recursion body
    public boolean helper(char[][] board, int row, int col){
    
        //In the two for loop, if I change i = row and j = col to i = 0 and j = 0
        //respectively, the program returns the right answer.
        for(int i = row; i < 9 ; ++i){
            for(int j = col; j < 9; ++j){
                if(board[i][j] == '.'){
                    for(char ch = '1'; ch <= '9'; ch++){
                        if(check(board, i, j, ch)){
                            board[i][j] = ch;
                            if(helper(board, i, j)){
                                return true;
                            }else{
                            board[i][j] = '.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
    return true;
}

    //check if the character to be filled is right.
    public boolean check(char[][] board, int row, int col, char ch){
        for(int i = 0; i < 9; ++i){
            if(board[row][i] == ch){
                return false;
            }
            if(board[i][col] == ch){
                return false;
            }
        }
        for(int i = row / 3 * 3; i < row / 3 * 3+ 3; ++i){
            for(int j = col / 3 * 3; j < col / 3 * 3 + 3; ++j){
                if(board[i][j] == ch){
                    return false;
                }
            }
        }
        return true;
    }
}   
    
    

That piece of code does not pass the OJ, but if I change the first two for loops in helper function to:

for(int i = 0; i < 9 ; ++i){
    for(int j = 0; j < 9; ++j){
    ...
    }
}

That works. I am really puzzled by that. since in the for loops, before i and j comes to row and col, the function actually does nothing other than iterating the values. Could someone tell me why this make a difference?

I read a lot of articles about recursion but I'm still not sure about the problem, could someone help me?

Answer 1

I print i and j under the two for loops and found that the problem is because if I call helper(i, j) each time. the value of j can only increase, it can not be decreased.