Solution: Sudoku Solver

Statement

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.

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 ...