Implementing the Backtracking Solution

Introduction

Backtracking is a general algorithmic technique that searches every possible combination to solve an optimization problem. Backtracking is also known as a depth-first search and branch and bound. The recursion technique is always used to solve backtracking problems.

To learn more about recursion and backtracking, you can check What is Recursion and N-Queen problem.

Solution approach

Like most kinds of backtracking problems, Sudoku can also be solved by assigning numbers one by one to empty cells. We need to make sure the following conditions are met before assigning a number to any empty cell:

• Check whether we can safely assign a number to an empty cell. In other words, check that the number assigned is not present already in the current row, column, or $3 \times 3$ sub-grid.

• Now if the above condition is passed, then we can assign the number, and recursively check whether this assigned number leads to a solution or not. If it doesn’t lead to a solution, then we need to try the next number for the current empty cell.

• It can be assumed that there will always be a solution to the Sudoku question displayed on the web page since it is coming from an API call, and the API is sending a solvable Sudoku puzzle.

Now let's implement each of the functionalities discussed above.

Check whether it's safe to assign a number to an empty cell

We will create a function isSafeToAssign(), which will accept the following parameters:

• board: This is the board containing the Sudoku question. It is essentially the 2D matrix that stores the Sudoku, in which a few of the cells are already filled and the rest are empty (their value is equal to 0).

• row: This is the current row of the Sudoku board on which we are trying to place the number.

• col: This is the current column of the Sudoku board on which we are trying to place the number.

• number: This is the number (ranging from 1 to 9) that we are trying to place at the (row, col) position of the 2D matrix.

Now let's implement the function.