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