sudoku solver

sudoku

values = [[None for _ in range(9)] for _ in range(9)]
taken = [[set() for _ in range(9)] for _ in range(9)]
free = set((i, j) for i in range(9) for j in range(9))

def set_val(i, j, val):
    assert(val not in taken[i][j])
    values[i][j] = val
    free.remove((i,j))
    for k in range(9):
        taken[i][k].add(val)
        taken[k][j].add(val)
        taken[i-i%3+k//3][j-j%3+k%3].add(val)

def unset_val(i, j, val):
    values[i][j] = None
    free.add((i,j))
    for k in range(9):
        taken[i][k].remove(val)
        taken[k][j].remove(val)
        taken[i-i%3+k//3][j-j%3+k%3].remove(val)

def choose():
    c = -1
    choice = None
    for (i,j) in free:
        if c < len(taken[i][j]):
            c = len(taken[i][j])
            choice = (i, j)
    assert choice is not None
    return choice

def print_board():
    for i in range(9):
        print(' '.join(str(values[i][j]) for j in range(9)))

def solve():
    if not free:
        return True
    i,j = choose()
    if len(taken[i][j]) == 9:
        return False
    for val in range(1,10):
        if val not in taken[i][j]:
            set_val(i, j, val)
            if solve():
                return True
            unset_val(i, j, val)


N = None
x = [
    [4,3,N,2,N,5,8,7,9],
    [N,N,N,N,N,N,5,N,N],
    [N,N,5,N,N,N,N,2,N],
    [N,N,N,5,N,4,9,N,7],
    [8,4,N,1,N,N,N,N,2],
    [N,2,7,N,9,N,N,N,N],
    [N,5,2,7,8,N,N,3,N],
    [N,N,N,4,5,N,N,N,8],
    [N,N,4,N,N,2,N,N,5]
]

for i in range(9):
    for j in range(9):
        if x[i][j] is not None:
            set_val(i, j, x[i][j])

if solve():
    print_board()
else:
    print('Unsolvable')