Skip to content

Instantly share code, notes, and snippets.

@unworthyEnzyme
Created December 28, 2024 13:42
Show Gist options
  • Save unworthyEnzyme/7b94de85468f210d5242fdd65a58d942 to your computer and use it in GitHub Desktop.
Save unworthyEnzyme/7b94de85468f210d5242fdd65a58d942 to your computer and use it in GitHub Desktop.
sudoku solver
import os
from typing import List, Tuple
import itertools
possibilities = set([1, 2, 3, 4, 5, 6, 7, 8, 9])
def solve(board: List[List[int]]) -> List[List[int]] | None:
if is_solved(board):
return board
moves, i, j = find_cell_with_least_moves(board)
if len(moves) == 0:
return None
for move in sorted(moves):
board[i][j] = move
result = solve(board)
if result != None:
return result
# we hit a dead end, backtrack.
board[i][j] = 0
return None
def find_cell_with_least_moves(board: List[List[int]]) -> Tuple[set, int, int]:
result = (possibilities, -1, -1)
n = len(board)
for i in range(n):
for j in range(n):
if board[i][j] != 0:
continue
moves = calculate_moves(board, i, j)
if len(moves) < len(result[0]):
result = (moves, i, j)
if len(moves) == 0:
return moves, i, j
return result
def calculate_moves(board: List[List[int]], i: int, j: int) -> set:
return possibilities - set(
row_nums(board, i) + col_nums(board, j) + inner_grid_nums(board, i, j)
)
def filter_zeroes(ns: List[int]) -> List[int]:
return [n for n in ns if n != 0]
def is_solved(board: List[List[int]]) -> bool:
return 0 not in itertools.chain(*board)
def inner_grid_nums(board: List[List[int]], i, j) -> List[int]:
r = (i // 3) * 3
c = (j // 3) * 3
row_section = board[r : r + 3]
mini_board = [row[c : c + 3] for row in row_section]
return filter_zeroes(list(itertools.chain(*mini_board)))
def row_nums(board: List[List[int]], i) -> List[int]:
return filter_zeroes(board[i])
def col_nums(board: List[List[int]], j) -> List[int]:
return filter_zeroes([row[j] for row in board])
def board_to_string(board):
result = []
for i in range(len(board)):
if i % 3 == 0 and i != 0:
result.append("- - - - - - - - - - - -")
row = []
for j in range(len(board[0])):
if j % 3 == 0 and j != 0:
row.append("|")
row.append(str(board[i][j] if board[i][j] != 0 else "."))
result.append(" ".join(row))
return "\n".join(result)
def clear_screen():
# For Windows
if os.name == "nt":
_ = os.system("cls")
# For Unix/Linux/MacOS
else:
_ = os.system("clear")
board = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 7, 0, 9, 0, 0],
[0, 3, 0, 0, 4, 0, 0, 0, 6],
[2, 0, 0, 0, 0, 0, 0, 0, 5],
[9, 0, 0, 0, 6, 0, 0, 0, 7],
[0, 0, 1, 0, 5, 7, 0, 0, 3],
[0, 0, 2, 4, 0, 0, 6, 0, 0],
[4, 0, 0, 0, 1, 0, 8, 0, 0],
[0, 0, 0, 5, 0, 2, 0, 0, 0],
]
print(board_to_string(solve(board)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment