Sudoku Solver (Backtracking)
This utility solves a 9x9 Sudoku puzzle using the Backtracking algorithm. It demonstrates recursion and constraint satisfaction.
Modules Used:
- Standard Library only.
The Algorithm
- Find an empty cell: Look for a cell containing
0. - Try numbers 1-9: Attempt to place a number in the empty cell.
- Check validity: Ensure the number doesn't exist in the current row, column, or 3x3 subgrid.
- Recurse: If valid, move to the next empty cell.
- Backtrack: If the recursion fails (leads to an unsolvable state), reset the cell to
0and try the next number.
The Code
Save this as sudoku.py.
def print_board(board):
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):
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 valid(board, num, pos):
# Check row
for i in range(len(board[0])):
if board[pos[0]][i] == num and pos[1] != i:
return False
# Check column
for i in range(len(board)):
if board[i][pos[1]] == num and pos[0] != i:
return False
# Check 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(board):
find = find_empty(board)
if not find:
return True
else:
row, col = find
for i in range(1, 10):
if valid(board, i, (row, col)):
board[row][col] = i
if solve(board):
return True
board[row][col] = 0
return False
if __name__ == "__main__":
# Example Board (0 represents empty cells)
board = [
[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("Original Board:")
print_board(board)
print("\nSolving...\n")
solve(board)
print("Solved Board:")
print_board(board)Usage
python sudoku.py