Given a 9 x 9 sudoku board, solve the puzzle by completing the empty cells. The sudoku board is only considered valid if the following rules are satisfied:

• Each row must contain digits between 1 and 9, and there should be no repetition of digits within a row.

• Each column must contain digits between 1 and 9, and there should be no repetition of digits within a column.

• The board consists of 9 non-overlapping sub-boxes, each containing 3 rows and 3 columns. Each of these 3 x 3 sub-boxes must contain digits between 1 and 9, and there should be no repetition of digits within a sub-box.

Constraints:

• board.length $= 9$

• board[i].length $= 9$

• board[i][j] is a digit or ..

• The input board is guaranteed to have one solution.

The main strategy behind the algorithm for solving the Sudoku is backtracking. For each empty cell, we identify all possible numbers that could be placed there based on Sudoku's rules. We then place each possible number in the cell and recursively call the solver function to attempt to solve the rest of the board. If placing a number leads to an invalid board, we backtrack by removing the number and trying the next possibility. This process continues until the entire board is successfully filled.

To implement the algorithm, we first implement GetPossibleNumbers(), which, for a given cell $(i, j)$, finds and returns all possible numbers that could be placed at board[i][j]. To achieve this:

1. Determine all invalid entries—numbers that are already present in row $i$, column $j$, and the 3x3 sub-box containing the cell $(i, j)$.

2. Take the union of these invalid numbers.

3. Subtract them from the possible entries, which are $1–9$ to obtain the valid possibilities for that cell.

Another key function in the solution is the recursive function SolveSudokuRec(), which attempts to fill the board row by row, starting from the leftmost side of each row. This function implements the following main steps:

1. The base case for this function is when $i==9$. This indicates that the entire board has been filled, at this point we return TRUE.

2. If $j==9$ , the current row has been completely traversed, so we move to the next row by calling SolveSudokuRec(i+1, 0).

3. For every filled cell (i.e., board[i][j] != "."), we simply proceed to the next cell by calling SolveSudokuRec(i, j+1).

4. For each empty cell, we determine all possible numbers that could be placed there using the GetPossibleNumbers() helper function. We then place each possible number in the cell and recursively move to the next one.

   1. If this call returns TRUE, we return TRUE as well.

   2. Otherwise, we backtrack by removing the number and trying the next option.

Let’s look at the following illustration to get a better understanding of the solution: