Of course! Here is a complete, well-commented, and efficient Sudoku solver in Python.
（图片来源网络，侵删）
I'll provide two versions:
- A Backtracking Solver: This is the most common and intuitive algorithm for solving Sudoku. It's easy to understand and works perfectly for standard 9x9 puzzles.
- A More Performant Solver: This version uses a more advanced technique called Constraint Propagation (specifically, the "Naked Singles" strategy) combined with backtracking. It's significantly faster for harder puzzles as it avoids unnecessary guessing.
The Backtracking Solver (Recommended for most use cases)
This approach is like how a human might solve Sudoku: try a number, and if it leads to a contradiction, backtrack and try a different number.
The Logic
- Find an Empty Cell: Scan the board for the next empty cell (represented by
0). - Base Case: If there are no empty cells left, the puzzle is solved! Return
True. - Try Numbers: For the empty cell, try placing numbers from 1 to 9.
- Check Validity: For each number, check if it's a valid placement according to Sudoku rules (not in the same row, column, or 3x3 box).
- Recurse: If the number is valid, place it in the cell and recursively call the solver function to fill the next empty cell.
- Backtrack: If the recursive call returns
False(meaning it hit a dead end), it means the number we just placed was incorrect. So, we "backtrack" by resetting the cell to0and try the next number. - No Solution: If we've tried all numbers from 1 to 9 for a cell and none of them work, it means the puzzle is unsolvable from this state. Return
False.
The Code
def print_board(board):
"""Prints the Sudoku board in a visually appealing format."""
for i in range(len(board)):
if i % 3 == 0 and i != 0:
print("- - - - - - - - - - - - ")
for j in range(len(board[0])):
if j % 3 == 0 and j != 0:
print(" | ", end="")
if j == 8:
print(board[i][j])
else:
print(str(board[i][j]) + " ", end="")
def find_empty(board):
"""Finds the next empty cell (represented by 0) in the board."""
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == 0:
return (i, j) # row, col
return None
def is_valid(board, num, pos):
"""Checks if a number is valid at a given position."""
# Check row
for j in range(len(board[0])):
if board[pos[0]][j] == num and pos[1] != j:
return False
# Check column
for i in range(len(board)):
if board[i][pos[1]] == num and pos[0] != i:
return False
# Check 3x3 box
box_x = pos[1] // 3
box_y = pos[0] // 3
for i in range(box_y * 3, box_y * 3 + 3):
for j in range(box_x * 3, box_x * 3 + 3):
if board[i][j] == num and (i, j) != pos:
return False
return True
def solve_sudoku(board):
"""Solves a Sudoku puzzle using backtracking."""
find = find_empty(board)
if not find:
return True # Board is full, puzzle is solved
else:
row, col = find
for i in range(1, 10):
if is_valid(board, i, (row, col)):
board[row][col] = i
if solve_sudoku(board):
return True
# Backtrack if the solution wasn't found
board[row][col] = 0
return False # Triggers backtracking
# --- Example Usage ---
if __name__ == "__main__":
# 0 represents empty cells
puzzle = [
[7, 8, 0, 4, 0, 0, 1, 2, 0],
[6, 0, 0, 0, 7, 5, 0, 0, 9],
[0, 0, 0, 6, 0, 1, 0, 7, 8],
[0, 0, 7, 0, 4, 0, 2, 6, 0],
[0, 0, 1, 0, 5, 0, 9, 3, 0],
[9, 0, 4, 0, 6, 0, 0, 0, 5],
[0, 7, 0, 3, 0, 0, 0, 1, 2],
[1, 2, 0, 0, 0, 7, 4, 0, 0],
[0, 4, 9, 2, 0, 6, 0, 0, 7]
]
print("Puzzle to solve:")
print_board(puzzle)
print("\nSolving...\n")
if solve_sudoku(puzzle):
print("Solved successfully!")
print_board(puzzle)
else:
print("No solution exists for this puzzle.")
The More Performant Solver (Constraint Propagation + Backtracking)
This solver is much faster for difficult puzzles. Before resorting to guessing (backtracking), it tries to fill in cells where only one possible number can go. This is called finding "Naked Singles."
The Logic
- Create Helper Structures: We first build lists to keep track of all possible numbers for each empty cell (
possibilities). We also create sets for the numbers already present in each row, column, and box. - Propagate Constraints: We scan the board and fill in any "Naked Singles" we find. A "Naked Single" is a cell that has only one possible number remaining. When we fill a cell, we update the possibilities for all other cells in the same row, column, and box. This process can sometimes fill in other "Naked Singles," creating a chain reaction.
- Check for Stalemate: If we go through the board and can't fill any more "Naked Singles," we stop the propagation.
- Backtrack: If the board is not yet full, we pick the cell with the fewest remaining possibilities (to minimize branching) and make a guess. We then recursively call the solver, which will first try to propagate constraints again from that new state.
- Base Case: If the board is full, we have a solution.
The Code
def solve_sudoku_fast(board):
"""
Solves a Sudoku puzzle using a more efficient backtracking algorithm
with constraint propagation (Naked Singles).
"""
# 1. Initialize helper data structures
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
possibilities = [[set() for _ in range(9)] for _ in range(9)]
empty_cells = []
# 2. Populate initial state
for r in range(9):
for c in range(9):
num = board[r][c]
if num == 0:
empty_cells.append((r, c))
possibilities[r][c] = set(range(1, 10))
else:
rows[r].add(num)
cols[c].add(num)
box_idx = (r // 3) * 3 + (c // 3)
boxes[box_idx].add(num)
# 3. Propagate constraints (find and fill Naked Singles)
def propagate_changes():
changed = True
while changed:
changed = False
for r, c in empty_cells:
if not possibilities[r][c]:
return False # Contradiction found, no solution
# Remove existing numbers from possibilities
possibilities[r][c] -= rows[r]
possibilities[r][c] -= cols[c]
box_idx = (r // 3) * 3 + (c // 3)
possibilities[r][c] -= boxes[box_idx]
if len(possibilities[r][c]) == 1:
# Naked Single found!
num = possibilities[r][c].pop()
board[r][c] = num
rows[r].add(num)
cols[c].add(num)
boxes[box_idx].add(num)
empty_cells.remove((r, c))
changed = True
return True
# Initial propagation
if not propagate_changes():
return False
#
（图片来源网络，侵删）
