from copy import deepcopy

grid = "003020600900305001001806400008102900700000008006708200002609500800203009005010300"

def parse_grid(grid):
    _grid = []
    for line in (grid[0+i:9+i] for i in range(0, len(grid), 9)):
        row = []
        _grid.append(row)
        for char in line:
            if char == '0':
                row.append([1,2,3,4,5,6,7,8,9])
            else:
                row.append(int(char))
    return _grid

def is_in_square(n, grid, square):
    for x in range(square[0], square[0]+3):
        for y in range(square[1], square[1]+3):
            if type(grid[y][x]) == int and grid[y][x] == n:
                return True
    return False

def is_in_row(n, grid, row):
    for x in range(0, 9):
        if type(grid[row][x]) == int and grid[row][x] == n:
            return True
    return False

def is_in_column(n, grid, column):
    for y in range(0, 9):
        if type(grid[y][column]) == int and grid[y][column] == n:
            return True
    return False

def find_pair(grid):
    return ((x, y) for y, row in enumerate(grid) for x, tile in enumerate(row) if type(tile) != int and len(tile) == 2)

def sudoku(grid, _tried={}):
    incomplete = False
    changed = False
    for y, row in enumerate(grid):
        for x, tile in enumerate(row):
            if type(tile) == int:
                continue
            tile = [n for n in tile if not (is_in_column(n, grid, x) or is_in_row(n, grid, y) or is_in_square(n, grid, (x//3*3, y//3*3)))]
            if len(tile) == 1:
                grid[y][x] = tile[0]
                changed = True
            elif len(tile) == 0:
                grid[y][x] = tile
                raise Exception
            else:
                grid[y][x] = tile
                incomplete = True

    if not changed:
        for pair in find_pair(grid):
            if pair in _tried:
                continue
            else:
                _tried[pair] = True
            x, y = None, None
            (x, y) = pair
            choices = grid[y][x]
            try:
                attempt = deepcopy(grid)
                attempt[y][x] = choices[0]
                return sudoku(attempt, _tried)
            except Exception:
                attempt = deepcopy(grid)
                attempt[y][x] = choices[1]
                try:
                    return sudoku(attempt, _tried)
                except Exception:
                    continue
            raise Exception

    if incomplete:
        return sudoku(grid, _tried)
    return grid

total = 0
with open('files/96.txt', 'r') as f:
    for line in f:
        result = sudoku(parse_grid(line[:-1]))
        total += result[0][0]*100 + result[0][1]*10 + result[0][2]
        print(result[0][0]*100 + result[0][1]*10 + result[0][2])
print(total)