Stuck in Sudoku backtracking solver (Java)
<p>I have been trying to figure out my mistake in the Sudoku backtracking solver for three days. The problem is from leetcode <a href="https://leetcode.com/problems/sudoku-solver/" rel="nofollow noreferrer">Sudoku Solver</a>. </p>

<p>My solver is based on the deduction in the attached picture. The problem is that my board is changed even if a path from root to leaf is invalid. </p>

<p>In other words, after it goes through an invalid path, the values it attempted are fixed in my original board. However, I only update my original board when its children returns true ( see the part in helper method: // put a number and generate children). </p>

<p>Basically, for each '.', I generate all possibilities from 1 to 9, construct a temp board which fills the current '.' with one possibility, then call helper of the next '.' with temp board.  I know it is not good to store a same size boardTemp for each possible child because of space cost, but my main concern now is to solve the problem first before optimizing the cost. </p>

<p>All in all, why is my board changing even if all children is not valid?</p>

<p>For example, base on the initial board  </p>

<p>..9748...; 7........; .2.1.9...; </p>

<p>..7...24.; .64.1.59.; .98...3..; </p>

<p>...8.3.2.; ........6; ...2759..;  </p>

<p>I got the final result after I run:  </p>

<p>139748652; 745326189; 826159437; </p>

<p>35769.24.; .64.1.59.; .98...3..; </p>

<p>...8.3.2.; ........6; ...2759..;  </p>

<pre><code>public void sudokuSolver(char[][] board) {
    for (int i = 0 ; i &lt; board.length ; i++) {
        for (int j = 0 ; j &lt; board.length ; j++) {
            if (board[i][j] == '.') {
                // find the first '.' as root
                helper(i, j, board);
                return;
            }
        }
    }
}

private boolean helper(int row, int col, char[][] board) {
    // case 2. check if it has following '.' and store its position
    boolean hasNext = false;
    boolean nextSearching = false;
    int nextRow = row;
    int nextCol = col;
    for (int i = 0 ; i &lt; board.length ; i++) {
        for (int j = 0; j &lt; board.length ; j++) {
            if (nextSearching &amp;&amp; !hasNext &amp;&amp; board[i][j] == '.') {
                hasNext = true; // there is next!
                nextRow = i;
                nextCol = j;
            }
            if (i == row &amp;&amp; j == col) {
                nextSearching = true;
            }
        }
    }

    // exit condition: last '.'
    if (!hasNext) {
        for (char put = '1' ; put &lt;= '9' ; put ++) {
            if (isValid(row, col, board, put)) {
                return true;
            }
        }
        return false;
    }

    // put a number and generate children
    for (char put = '1' ; put &lt;= '9' ; put ++) {
        if (isValid(row, col, board, put)) {
            char[][] boardTemp = board;
            boardTemp[row][col] = put;
            boolean valid = helper(nextRow, nextCol, boardTemp);
            if (valid) {
                // board is supposed to change only when valid is true.
                board[row][col] = put;
                return true;
            }
        }
    }
    return false;
}

private boolean isValid(int row, int col, char[][] board, char c) {
    // go through each row, column, and subblock to determine if c is a valid choice based on current board.
    for (int jCol = 0 ; jCol &lt; 9 ; jCol ++) {
        if (board[row][jCol] == c) {
            return false;
        }
    }
    for (int iRow = 0 ; iRow &lt; 9 ; iRow ++) {
        if (board[iRow][col] == c) {
            return false;
        }
    }
    for (int i = row/3*3 ; i &lt; row/3*3 + 3 ; i++) {
        for (int j = col/3*3 ; j &lt; col/3*3 + 3 ; j++) {
            if (board[i][j] == c) {
                return false;
            }
        }
    }
    return true;
}
</code></pre>

<p><a href="https://i.stack.imgur.com/aWJYr.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/aWJYr.jpg" alt="My tree for backtracking"></a></p>