This content originally appeared on DEV Community and was authored by Melissa
Creating sudoku solvers can be a great way to familiarize yourself with recursive backtracking and algorithm solving. In this blog post, we'll explore the some helper functions from a command-line Sudoku game project I created to demonstrate these methods. This file contains essential helper functions that facilitate solving Sudoku puzzles. We'll break down the key functions: is_valid, find_empty, and solve.
Checking Validity of a Number
The is_valid function checks whether placing a specific number in a given cell is valid according to Sudoku rules.
def is_valid(board, row, col, num):
# Check if the number is not present in the same row and column
if num in board[row] or num in [board[i][col] for i in range(9)]:
return False
start_row, start_col = 3 * (row // 3), 3 * (col // 3)
for i in range(start_row, start_row + 3):
for j in range(start_col, start_col + 3):
if board[i][j] == num:
return False
return True
Row and Column Check: Ensures the number is not already present in the same row or column.
Subgrid Check: Ensures the number is not present in the 3x3 subgrid.
Finding an Empty Cell
The find_empty function locates the next empty cell (represented by 0) on the board.
def find_empty(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
return (i, j)
return None
Iteration: Iterates through the board to find an empty cell.
Return: Returns the coordinates of the first empty cell found or None if the board is full.
Solving the Sudoku Puzzle
The solve function uses backtracking to solve the Sudoku puzzle.
def solve(board):
empty_cell = find_empty(board)
# Board is solved
if not empty_cell:
return board
row, col = empty_cell
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
random.shuffle(numbers)
for num in numbers:
if is_valid(board, row, col, num):
board[row][col] = num
if solve(board):
return board
# Backtrack if current placement doesn't lead to a solution
board[row][col] = 0
# No valid number for current empty cell
return False
Find Empty Cell: Uses find_empty to locate the next empty cell.
Backtracking: Tries placing numbers 1-9 in the empty cell, checking validity with is_valid.
Recursive Solve: Recursively attempts to solve the board. If a placement leads to a solution, it returns the solved board.
Backtrack: If a placement doesn't lead to a solution, it resets the cell and tries the next number.
Conclusion
Helper functions are crucial for the functionality of our Sudoku solver. The is_valid function ensures that the Sudoku rules are followed, find_empty helps locate the next cell to fill, and solve uses recursive backtracking to find the solution. Understanding these helper functions provides insight into the logic behind solving Sudoku puzzles programmatically.
This content originally appeared on DEV Community and was authored by Melissa
Melissa | Sciencx (2024-10-24T17:20:38+00:00) Sudoku Solving in Python. Retrieved from https://www.scien.cx/2024/10/24/sudoku-solving-in-python/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.