Building a Sudoku Solver in Python

Sudoku Solver Implementation

Step 1: Create a Sudoku Board Representation

To represent the Sudoku board, we will use a 2D list. Each cell will store the digit present at that position, or 0 if the cell is empty. Here's an example of a Sudoku board representation:

board = [
[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]
]

Step 2: Implement a Function to Check Validity of a Digit

We need a function to check if a digit is valid in a specific cell. This function will take the current board state, a row index, a column index, and a digit as parameters. It will check if the digit is already present in the current row, column, or 3x3 grid, and return False if it violates the Sudoku rules. Here's an example implementation:

def is_valid(board, row, col, digit):
# Check if digit is present in the row
for i in range(9):
if board[row][i] == digit:
return False
# Check if digit is present in the column
for i in range(9):
if board[i][col] == digit:
return False
# Check if digit is present in the 3x3 grid
start_row = (row // 3) * 3
start_col = (col // 3) * 3
for i in range(3):
for j in range(3):
if board[start_row + i][start_col + j] == digit:
return False
return True

Step 3: Implement the Backtracking Function

The backtracking function will be responsible for solving the Sudoku puzzle recursively. It will start by finding an empty cell (a cell with a value of 0) in the board. Here's the outline of the backtracking function:

def solve_sudoku(board):
# Find an empty cell
empty_cell = find_empty_cell(board)
if not empty_cell:
return True  # Base case: Puzzle solved
row, col = empty_cell
for digit in range(1, 10):
if is_valid(board, row, col, digit):
board[row][col] = digit
if solve_sudoku(board):
return True
board[row][col] = 0  # Undo the placement
return False  # Backtrack

Step 4: Implement the Helper Function to Find an Empty Cell

We need a helper function to find the next empty cell in the Sudoku board. This function will iterate through the board and return the row and column indices of the first empty cell it encounters. If no empty cell is found, it will return `None`. Here's an example implementation:

def find_empty_cell(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
return i, j
return None

Step 5: Test the Sudoku Solver

Now, we can test our Sudoku solver by providing a puzzle and calling the `solve_sudoku` function. Let's use the provided puzzle and print the solved board:

board = [
[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]
]
if solve_sudoku(board):
print("Sudoku puzzle solved:")
for row in board:
print(row)
else:
print("No solution found for the Sudoku puzzle.")

Congratulations! You have successfully built a Sudoku solver using a backtracking algorithm in Python. The backtracking algorithm efficiently searches for valid digits and backtracks if no valid digit is found, allowing us to solve even complex Sudoku puzzles. Feel free to experiment further by generating new puzzles, adding a user interface, or exploring other Sudoku-solving techniques.

In this article, we covered the basics of implementing a Sudoku solver in Python. We discussed the Sudoku board representation, the validation function, the backtracking algorithm, and how to test the solver with a puzzle.

Thank you for reading, and happy Sudoku solving!

Published on May 19, 2023

Tags: Python