sudoku.py

#!/usr/bin/env python3

import re

start = """
    8........
    ..36.....
    .7..9.2..
    .5...7...
    ....457..
    ...1...3.
    ..1....68
    ..85...1.
    .9....4..
"""

start_ = """
    .65.3.2..
    2.4.....3
    .......1.
    ..175....
    8.......1
    ....497..
    .8.......
    1.....8.6
    ..9.1.57.
"""

start_ = """
    6..1.82.3
    .2..4..9.
    8.3..54..
    5.46.7..9
    .3.....5.
    7..8.31.2
    ..17..9.6
    .8..3..2.
    3.29.4..5
"""

def no_zeros(l):
    return set(n for n in l if n != 0)

def row_nums(board, y):
    return no_zeros(board[y*9:y*9 + 9])

def col_nums(board, x):
    return no_zeros(board[x:x + 8*9 + 1:9])

def block_nums(board, x, y):
    x -= (x % 3)
    y -= (y % 3)

    return no_zeros(
        board[y*9 + x:y*9 + x + 3]
        + board[(y + 1)*9 + x:(y + 1)*9 + x + 3]
        + board[(y + 2)*9 + x:(y + 2)*9 + x + 3])

all_set = set(range(1, 10))
def find_possible(board):
    return [all_set.difference(
        row_nums(board, y)
            .union(col_nums(board, x))
            .union(block_nums(board, x, y)))
        if board[y*9 + x] == 0
        else board[y*9 + x]
        for y in range(0, 9)
        for x in range(0, 9)]

def find_best_poss(poss):
    idx = -1
    best = 10
    
    for i, n in enumerate(poss):
        if type(n) == int:
            continue

        if len(n) == 1:
            return i
    
        if len(n) < best:
            idx = i
            best = len(n)

    return idx

def replace(board, idx, n):
    new_board = list(board)
    new_board[idx] = n
    return new_board

def solve(board):
    poss = find_possible(board)

    idx = find_best_poss(poss)
    if idx == -1:
        return board

    num = len(poss[idx])
    if num == 1:
        return solve(replace(board, idx, list(poss[idx])[0]))
    elif num > 1:
        for c in list(poss[idx]):
            cboard = replace(board, idx, c)

            r = solve(cboard)
            if r:
                return r
        
    return None

def pretty_print(board):
    import textwrap

    print("\n".join(textwrap.wrap("".join(str(n) for n in board), 9)))

pretty_print(solve([
    0 if c == "."
    else int(c)
    for c in re.sub("[^0-9.]", "", start)]))