Sudoku Solver in Python
Intermediate · Logic and puzzles · about 60 minutes to build · 149 lines
Type a Sudoku puzzle row by row, or use the built-in one, and the program fills in every empty cell.
The program
Press Run and answer its questions in the box that appears under the code.
sudoku_solver.py
"""Sudoku solver: fill in any 9x9 puzzle with backtracking."""
SIZE = 9
BOX = 3
BLANKS = "0._" # characters that mean an empty cell when you type a puzzle
ALLOWED = "123456789" + BLANKS
MAX_TRIES = 150_000 # give up after this many tries (digits placed)
EXAMPLE = [
"530070000",
"600195000",
"098000060",
"800060003",
"400803001",
"700020006",
"060000280",
"000419005",
"000080079",
]
# --- Reading a puzzle ---
def parse_row(text):
"""Turn "53..7...." into [5, 3, 0, 0, 7, 0, 0, 0, 0], or None."""
text = text.replace(" ", "").replace("|", "")
if len(text) != SIZE or not all(char in ALLOWED for char in text):
return None
return [0 if char in BLANKS else int(char) for char in text]
def read_puzzle():
"""Ask for the 9 rows of a puzzle, asking again for any invalid row."""
print("Type 9 characters per row: digits, and . or 0 for an empty cell.")
board = []
while len(board) < SIZE:
row = parse_row(input(f"Row {len(board) + 1}: "))
if row is None:
print("A row needs exactly 9 digits or dots, like 53..7....")
else:
board.append(row)
return board
# --- The rules and the search ---
def can_place(board, row, col, digit):
"""Check that digit is not already in this row, column or 3x3 box."""
if digit in board[row]:
return False
if any(board[r][col] == digit for r in range(SIZE)):
return False
top, left = row - row % BOX, col - col % BOX
return all(board[r][c] != digit
for r in range(top, top + BOX) for c in range(left, left + BOX))
def find_empty(board):
"""Return (row, col) of the first empty cell, or None if there is none."""
for row in range(SIZE):
for col in range(SIZE):
if board[row][col] == 0:
return row, col
return None
def solve(board, stats):
"""Fill the board by trying digits and undoing the ones that fail."""
cell = find_empty(board)
if cell is None:
return True # no empty cells left: solved
row, col = cell
for digit in range(1, SIZE + 1):
if stats["tries"] >= MAX_TRIES:
return False # taking too long: give up
if can_place(board, row, col, digit):
board[row][col] = digit
stats["tries"] += 1
if solve(board, stats):
return True
board[row][col] = 0 # dead end: undo it and try the next digit
return False # no digit fits here, so an earlier guess was wrong
def clues_are_valid(board):
"""Check that the given digits do not already break the rules."""
for row in range(SIZE):
for col in range(SIZE):
digit = board[row][col]
if digit:
board[row][col] = 0 # lift it out to check it against the rest
ok = can_place(board, row, col, digit)
board[row][col] = digit
if not ok:
return False
return True
# --- Showing the result ---
def board_lines(board):
"""Draw the board as text lines with a line between the 3x3 boxes."""
lines = []
for row in range(SIZE):
if row and row % BOX == 0:
lines.append("------+-------+------")
cells = [str(n) if n else "." for n in board[row]]
boxes = [" ".join(cells[i:i + BOX]) for i in range(0, SIZE, BOX)]
lines.append(" | ".join(boxes))
return lines
def solve_and_show(board):
"""Solve a puzzle and print it next to its solution."""
if not clues_are_valid(board):
print("Two clues clash: a digit repeats in a row, column or box.")
return
puzzle = board_lines(board)
stats = {"tries": 0}
if not solve(board, stats):
if stats["tries"] >= MAX_TRIES:
print(f"No solution found in {MAX_TRIES:,} tries, so I stopped.")
else:
print("This puzzle has no solution.")
return
print(f"\n{'Puzzle':<21} Solution")
for left, right in zip(puzzle, board_lines(board)):
print(f"{left:<21} {right}")
print(f"Solved in {stats['tries']:,} tries.") # a try = one digit placed
def main():
"""Show the menu until the user quits."""
print("Sudoku solver")
while True:
print("\n1) Solve the example 2) Type a puzzle 3) Quit")
choice = input("Choose 1-3: ").strip()
if choice == "1":
solve_and_show([parse_row(line) for line in EXAMPLE])
elif choice == "2":
solve_and_show(read_puzzle())
elif choice == "3":
print("Goodbye.")
break
else:
print("Please type 1, 2 or 3.")
if __name__ == "__main__":
main()
Open it in the full editor to save it, share it and keep building.
Sample run
What the program printed, and what was typed (in yellow).
Sudoku solver 1) Solve the example 2) Type a puzzle 3) Quit Choose 1-3: 1 Puzzle Solution 5 3 . | . 7 . | . . . 5 3 4 | 6 7 8 | 9 1 2 6 . . | 1 9 5 | . . . 6 7 2 | 1 9 5 | 3 4 8 . 9 8 | . . . | . 6 . 1 9 8 | 3 4 2 | 5 6 7 ------+-------+------ ------+-------+------ 8 . . | . 6 . | . . 3 8 5 9 | 7 6 1 | 4 2 3 4 . . | 8 . 3 | . . 1 4 2 6 | 8 5 3 | 7 9 1 7 . . | . 2 . | . . 6 7 1 3 | 9 2 4 | 8 5 6 ------+-------+------ ------+-------+------ . 6 . | . . . | 2 8 . 9 6 1 | 5 3 7 | 2 8 4 . . . | 4 1 9 | . . 5 2 8 7 | 4 1 9 | 6 3 5 . . . | . 8 . | . 7 9 3 4 5 | 2 8 6 | 1 7 9 Solved in 4,208 tries. 1) Solve the example 2) Type a puzzle 3) Quit Choose 1-3: 2 Type 9 characters per row: digits, and . or 0 for an empty cell. Row 1: ..3.2.6.. Row 2: 9..3.5..1 Row 3: ..18.64 A row needs exactly 9 digits or dots, like 53..7.... Row 3: ..18.64.. Row 4: ..81.29.. Row 5: 7.......8 Row 6: ..67.82.. Row 7: ..26.95.. Row 8: 8..2.3..9 Row 9: ..5.1.3.. Puzzle Solution . . 3 | . 2 . | 6 . . 4 8 3 | 9 2 1 | 6 5 7 9 . . | 3 . 5 | . . 1 9 6 7 | 3 4 5 | 8 2 1 . . 1 | 8 . 6 | 4 . . 2 5 1 | 8 7 6 | 4 9 3 ------+-------+------ ------+-------+------ . . 8 | 1 . 2 | 9 . . 5 4 8 | 1 3 2 | 9 7 6 7 . . | . . . | . . 8 7 2 9 | 5 6 4 | 1 3 8 . . 6 | 7 . 8 | 2 . . 1 3 6 | 7 9 8 | 2 4 5 ------+-------+------ ------+-------+------ . . 2 | 6 . 9 | 5 . . 3 7 2 | 6 8 9 | 5 1 4 8 . . | 2 . 3 | . . 9 8 1 4 | 2 5 3 | 7 6 9 . . 5 | . 1 . | 3 . . 6 9 5 | 4 1 7 | 3 8 2 Solved in 200 tries. 1) Solve the example 2) Type a puzzle 3) Quit Choose 1-3: 3 Goodbye.
How it is built
1. Reading a row
A row is 9 characters: digits for the clues and ., 0 or _ for empty cells, which become 0 on the board. Spaces and | are removed first, so rows can be typed with gaps.
def parse_row(text): """Turn "53..7...." into [5, 3, 0, 0, 7, 0, 0, 0, 0], or None.""" text = text.replace(" ", "").replace("|", "") if len(text) != SIZE or not all(char in ALLOWED for char in text): return None return [0 if char in BLANKS else int(char) for char in text]
2. The three rules
A digit may go in a cell only if it is not already in the same row, the same column or the same 3x3 box. row - row % BOX gives the top row of the box (0, 3 or 6), and the same trick gives its left column.
def can_place(board, row, col, digit): """Check that digit is not already in this row, column or 3x3 box.""" if digit in board[row]: return False if any(board[r][col] == digit for r in range(SIZE)): return False top, left = row - row % BOX, col - col % BOX return all(board[r][c] != digit for r in range(top, top + BOX) for c in range(left, left + BOX))
3. Backtracking
The solver finds the first empty cell and tries the digits 1 to 9. When a digit fits, it is written in and solve calls itself to fill the rest of the board. If that fails, the digit is erased and the next one tried; if no digit fits, it returns False, and the call before it moves on to its own next digit.
def solve(board, stats): """Fill the board by trying digits and undoing the ones that fail.""" cell = find_empty(board) if cell is None: return True # no empty cells left: solved row, col = cell for digit in range(1, SIZE + 1): if stats["tries"] >= MAX_TRIES: return False # taking too long: give up if can_place(board, row, col, digit): board[row][col] = digit stats["tries"] += 1 if solve(board, stats): return True board[row][col] = 0 # dead end: undo it and try the next digit return False # no digit fits here, so an earlier guess was wrong
4. Checking the clues
A puzzle typed with two 5s in one row can never be solved, and the search could take a long time to find that out. So each clue is lifted out and checked against the others before solving starts.
def clues_are_valid(board): """Check that the given digits do not already break the rules.""" for row in range(SIZE): for col in range(SIZE): digit = board[row][col] if digit: board[row][col] = 0 # lift it out to check it against the rest ok = can_place(board, row, col, digit) board[row][col] = digit if not ok: return False return True
5. Drawing the board
Each row becomes a line of text with | between the boxes, and a dashed line goes in after every third row. Returning lines instead of printing them lets the puzzle and its solution sit side by side.
def board_lines(board): """Draw the board as text lines with a line between the 3x3 boxes.""" lines = [] for row in range(SIZE): if row and row % BOX == 0: lines.append("------+-------+------") cells = [str(n) if n else "." for n in board[row]] boxes = [" ".join(cells[i:i + BOX]) for i in range(0, SIZE, BOX)] lines.append(" | ".join(boxes)) return lines
6. Solving and showing
stats is a dictionary passed into solve, so the count of tries can grow inside every level of the recursion. MAX_TRIES stops a puzzle that would take too long.
def solve_and_show(board): """Solve a puzzle and print it next to its solution.""" if not clues_are_valid(board): print("Two clues clash: a digit repeats in a row, column or box.") return puzzle = board_lines(board) stats = {"tries": 0} if not solve(board, stats): if stats["tries"] >= MAX_TRIES: print(f"No solution found in {MAX_TRIES:,} tries, so I stopped.") else: print("This puzzle has no solution.") return print(f"\n{'Puzzle':<21} Solution") for left, right in zip(puzzle, board_lines(board)): print(f"{left:<21} {right}") print(f"Solved in {stats['tries']:,} tries.") # a try = one digit placed
Make it bigger
- Fill the empty cell with the fewest possible digits first, as people do, and compare how many tries it saves.
- Count all the solutions instead of stopping at the first, to check that a puzzle has only one.
- Make new puzzles: solve an empty board with the digits in random order, then remove clues.
- Accept a whole puzzle pasted as one line of 81 characters.
What it practises
- recursion
- backtracking
- lists of lists
- any() and all()
- list comprehensions