Backtracking Algorithm – Sudoku Solver

The purpose of this Python challenge is to demonstrate the use of a backtracking algorithm to solve a Sudoku puzzle.

Did You Know?

The objective of a Sudoku puzzle is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid (also called “boxes”) contains all of the digits from 1 to 9. A Sudoku puzzle is a partially completed grid, which for a well-posed puzzle has a single solution.

Backtracking Algorithm

A backtracking algorithm is a recursive algorithm that attempts to solve a given problem by testing all possible paths towards a solution until a solution is found. Each time a path is tested, if a solution is not found, the algorithm backtracks to test another possible path and so on till a solution is found or all paths have been tested.

The typical scenario where a backtracking algorithm is when you try to find your way out in a maze. Every time you reach a dead-end, you backtrack to try another path untill you find the exit or all path have been explored.

Backtracking algorithms can be used for other types of problems such as solving a Magic Square Puzzle or a Sudoku grid.

Backtracking algorithms rely on the use of a recursive function. A recursive function is a function that calls itself until a condition is met.

Note that there are other approaches that could be used to solve a Sudoku puzzle. The Backtracking approach may not always be the most effective but is used in this challenge to demonstrate how a backtracking algorithm behaves and how it can be implemented using Python.

Python Code

Extra Challenge:

An extra challenge would be to design an algorithm used to create a Sudoku Grid. The generated Sudoku grid should have enough clues (numbers in cells) to be solvable resulting in a unique solution.