Building a Sudoku Solver in Python

In this article, we will explore how to build a Sudoku solver using a backtracking algorithm in Python. Sudoku is a logic-based number puzzle where the goal is to fill a 9x9 grid with digits from 1 to 9, ensuring that each column, each row, and each of the nine 3x3 subgrids contain all of the digits from 1 to 9. We will implement a recursive backtracking algorithm to solve Sudoku puzzles efficiently. Let's dive in!

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

Related Posts

Did you enjoy this article? If you did here are some more articles that I thought you will enjoy as they are very similar to the article that you just finished reading.

Tutorials

Learn how to code in HTML, CSS, JavaScript, Python, Ruby, PHP, Java, C#, SQL, and more.

No matter the programming language you're looking to learn, I've hopefully compiled an incredible set of tutorials for you to learn; whether you are beginner or an expert, there is something for everyone to learn. Each topic I go in-depth and provide many examples throughout. I can't wait for you to dig in and improve your skillset with any of the tutorials below.