Sudoku is a popular number placement puzzle that rose to worldwide fame in the 2000s. The classic 9x9 grid consists of 9 subgrids called “regions” that each contain 9 cells. The puzzle begins with some cells prefilled with numbers between 1-9. To solve a Sudoku, you must fill the empty cells with numbers so that each row, column, and region contains the numbers 1-9 exactly once without repeating any numbers within those units.

In this comprehensive guide, we will walk through the steps to code a Python program that takes a valid, partially completed 9x9 Sudoku puzzle as input and outputs the solved puzzle by filling in the missing values. We will use techniques like recursion and backtracking to systematically place numbers while adhering to the Sudoku rules.

## Table of Contents

## Open Table of Contents

## Prerequisites

To follow along with this Sudoku solver tutorial, you should have:

- Basic knowledge of Python programming and experience with:
- Data structures like lists, tuples, dictionaries
- Control flow statements like if-else, for loops
- Functions
- Object-Oriented Programming concepts like classes

- A Python 3 interpreter installed on your system
- A text editor or IDE for writing and executing the Python code
- Some familiarity with recursion and backtracking algorithms

If you need to brush up on any Python basics, reviewing the Python documentation can help prepare you for this tutorial. Let’s get started building our Sudoku solver!

## Validating the Sudoku Puzzle Input

The first step is to check that the initial puzzle we want to solve is a valid Sudoku board. This ensures we are not trying to solve an impossible or incorrectly formatted puzzle.

We will represent the 9x9 Sudoku grid as a 2D list of lists in Python. Empty cells will be filled with 0 while pre-filled cells will have numbers 1-9:

```
puzzle = [[5,3,0,0,7,0,0,0,0],
[6,0,0,1,9,5,0,0,0],
[0,9,8,0,0,0,0,6,0],
[8,0,0,0,6,0,0,0,3],
[4,0,0,8,0,3,0,0,1],
[7,0,0,0,2,0,0,0,6],
[0,6,0,0,0,0,2,8,0],
[0,0,0,4,1,9,0,0,5],
[0,0,0,0,8,0,0,7,9]]
```

We will write a `validate_sudoku()`

function that returns `True`

if the puzzle is valid and `False`

otherwise. For a valid puzzle:

- Each row must have digits 1-9 without repeating any
- Each column must have digits 1-9 without repeating any
- Each 3x3 region must have digits 1-9 without repeating any

Here is the complete function to validate these rules:

```
def validate_sudoku(puzzle):
# Create sets for rows, cols and regions
rows = [set() for i in range(9)]
cols = [set() for i in range(9)]
regions = [[set() for _ in range(3)] for _ in range(3)]
for r in range(9):
for c in range(9):
val = puzzle[r][c]
# Check row
if val in rows[r]:
return False
rows[r].add(val)
# Check column
if val in cols[c]:
return False
cols[c].add(val)
# Check region
region_index = (r // 3, c // 3)
if val in regions[region_index[0]][region_index[1]]:
return False
regions[region_index[0]][region_index[1]].add(val)
# Puzzle is valid
return True
```

The `validate_sudoku()`

function above returns `True`

if the input puzzle passes all the validity checks. We create sets to track the row, column, and 3x3 region values and check for any duplicates which would make the puzzle invalid.

Let’s test it on a valid and invalid puzzle:

```
puzzle1 = [[5,3,0,0,7,0,0,0,0],
[6,0,0,1,9,5,0,0,0],
[0,9,8,0,0,0,0,6,0],
[8,0,0,0,6,0,0,0,3],
[4,0,0,8,0,3,0,0,1],
[7,0,0,0,2,0,0,0,6],
[0,6,0,0,0,0,2,8,0],
[0,0,0,4,1,9,0,0,5],
[0,0,0,0,8,0,0,7,9]]
print(validate_sudoku(puzzle1)) # True
puzzle2 = [[5,3,0,0,7,0,0,0,0],
[6,0,0,1,9,5,0,0,0],
[0,9,8,0,0,0,0,6,0],
[8,0,0,0,6,0,0,0,3],
[4,0,0,8,0,3,0,0,1],
[7,0,0,0,2,0,0,0,6],
[0,6,0,0,0,0,2,8,0],
[0,0,2,4,1,9,0,0,5],
[0,0,0,0,8,0,0,7,9]]
print(validate_sudoku(puzzle2)) # False (Duplicate 2 in 8th row)
```

This validation will prevent us from wasting time trying to solve invalid puzzles. Next, let’s focus on the solver!

## Solving the Sudoku Puzzle

Now we can start building the Sudoku solver using a recursive backtracking algorithm. The steps will be:

- Find an empty cell on the puzzle
- Try placing digits 1-9 in that cell
- Check if that digit is valid in the current spot based on Sudoku rules
- If valid, recursively call the solver on the updated puzzle to solve further
- If we find a conflict (digit not valid), backtrack and try a new number in the cell instead
- Repeat until the puzzle is solved!

### Finding the Next Empty Cell

We will need a helper function `find_next_empty()`

that scans the puzzle and returns the row and column index tuple `(r, c)`

of the next cell that is empty (has a value 0). This will be used to determine where to fill a number next.

```
def find_next_empty(puzzle):
# Get dimensions
n = len(puzzle)
# Scan row by row, col by col
for r in range(n):
for c in range(n):
if puzzle[r][c] == 0:
return r, c
# No empty cells left
return None, None
```

This scans the puzzle in order and returns the first empty cell found. If no empty cells remain, it returns `None, None`

indicating the puzzle is completely filled.

### Checking Validity of a Number in Cell

To check if a number is valid in a given cell, we can reuse parts of our `validate_sudoku()`

function earlier. We will make a `is_valid()`

helper that takes the puzzle, row, column, and value to check and returns True if placing that value in the cell is valid:

```
def is_valid(puzzle, r, c, val):
# Check if value in row
if val in puzzle[r]:
return False
# Check if value in column
if val in [puzzle[i][c] for i in range(9)]:
return False
# Get region indexes
r_start = (r // 3) * 3
c_start = (c // 3) * 3
# Check region
for i in range(3):
for j in range(3):
if puzzle[r_start + i][c_start + j] == val:
return False
# If no conflicts, valid
return True
```

This checks the row, column and 3x3 region to make sure `val`

does not already exist in any of those locations.

### Putting it Together in the Solver

Now we can use `find_next_empty()`

and `is_valid()`

in our recursive backtracking solver function:

```
def solve_sudoku(puzzle):
# Find next empty cell
r, c = find_next_empty(puzzle)
# Base case: no more empty cells
if r is None:
return True
# Try digits 1-9 in cell
for digit in range(1, 10):
# Check if valid
if is_valid(puzzle, r, c, digit):
# Set value and recursively solve rest of board
puzzle[r][c] = digit
if solve_sudoku(puzzle):
return True
# Undo and try again if failed
puzzle[r][c] = 0
# Could not solve with any number
return False
```

The recursive logic:

- Find the next empty cell with
`find_next_empty()`

- Try each digit 1-9 in that cell, using
`is_valid()`

to check - If we can set a valid digit without causing any conflicts, recursively call
`solve_sudoku()`

on the updated puzzle to progress forward - If the recursive call succeeds in fully solving the puzzle, return
`True`

for success! - If conflict found, reset the cell and try next digit
- If no valid digits work in cell, reset it and return
`False`

backtracking

This recursive depth-first search with backtracking allows us to systematically try all combinations until we find a solution that works!

### Testing the Solver

Let’s test the complete solver on some sample puzzles:

```
puzzle1 = [[5,3,0,0,7,0,0,0,0],
[6,0,0,1,9,5,0,0,0],
[0,9,8,0,0,0,0,6,0],
[8,0,0,0,6,0,0,0,3],
[4,0,0,8,0,3,0,0,1],
[7,0,0,0,2,0,0,0,6],
[0,6,0,0,0,0,2,8,0],
[0,0,0,4,1,9,0,0,5],
[0,0,0,0,8,0,0,7,9]]
print(solve_sudoku(puzzle1))
print(puzzle1)
# Prints:
# True
# [[5, 3, 4, 6, 7, 8, 9, 1, 2],
# [6, 7, 2, 1, 9, 5, 3, 4, 8],
# [1, 9, 8, 3, 4, 2, 5, 6, 7],
# [8, 5, 9, 7, 6, 1, 4, 2, 3],
# [4, 2, 6, 8, 5, 3, 7, 9, 1],
# [7, 1, 3, 9, 2, 4, 8, 5, 6],
# [9, 6, 1, 5, 3, 7, 2, 8, 4],
# [2, 8, 7, 4, 1, 9, 6, 3, 5],
# [3, 4, 5, 2, 8, 6, 1, 7, 9]]
```

Our Sudoku solver successfully solved the puzzle! The `solve_sudoku()`

function can work on any valid 9x9 puzzle, making it a flexible and reusable component for Sudoku implementations.

## Optimizing the Solver

There are further enhancements we can add to improve the efficiency and performance of the basic solver above:

### Trying Most Constrained Cells First

Instead of scanning the puzzle sequentially, we can prioritize empty cells that have the fewest possible digit options. This helps prune the search tree earlier.

We can count the number of allowed digits in each cell upfront using a helper function:

```
def count_allowed_values(puzzle, r, c):
# Initialize counter
counter = 0
# Check digits 1-9
for val in range(1,10):
if is_valid(puzzle, r, c, val):
counter += 1
return counter
```

Then find the cell with the minimum allowed values:

```
# Return cell (r, c) with fewest options
def find_most_constrained(puzzle):
n = len(puzzle)
min_options = 10
for r in range(n):
for c in range(n):
if puzzle[r][c] == 0:
num_options = count_allowed_values(puzzle, r, c)
if num_options < min_options:
min_r, min_c = r, c
min_options = num_options
return min_r, min_c
```

We replace our `find_next_empty()`

call with `find_most_constrained()`

to start with the most limited cell.

### Adding heuristics

We can add other heuristics like:

- Trying digits with least occurrences first
- Eliminating impossible candidates early
- Tracking solved cells to avoid retries

This can significantly reduce the search tree and improve performance.

## Conclusion

In this guide, we implemented a Sudoku solver in Python step-by-step using a backtracking algorithm. Key points included:

- Validating the initial puzzle
- Finding the next empty cell
- Checking if a digit can be placed in a cell
- Using recursion and backtracking to try all combinations
- Optimizing with constraints and heuristics

Sudoku puzzles have been mathematically proven to have only one valid solution. By using algorithms like this backtracking solver, we can systematically work towards the single solution without needing to guess. Mastering Sudoku solving is a great way to improve your logical thinking and programming abilities.