sodoku_solver.py

grid = [-1] * 81

print("Input sudoku, spaces for blank:")
for y in range(9):
    print("-" * 9)
    row = input()
    if len(row) > 9:
        print("Invalid input")
        exit()
    for x in range(len(row)):
        if ord('1') <= ord(row[x]) <= ord('9'):
            grid[9 * y + x] = ord(row[x]) - ord('1')
        elif not row[x].isspace():
            print("Invalid input")
            exit()


def is_solved(grid):
    for n in grid:
        if n == -1:
            return False
    return True


def is_allowed(grid, n, x, y):
    for dx in range(9):
        if dx != x and grid[9 * y + dx] == n:
            return False
    for dy in range(9):
        if dy != y and grid[9 * dy + x] == n:
            return False
    grid_x = (x // 3) * 3
    grid_y = (y // 3) * 3
    for dx in range(3):
        for dy in range(3):
            if (grid_x + dx != x or grid_y + dy != y) and grid[9 * (grid_y + dy) + (grid_x + dx)] == n:
                return False
    return True


def add_to_solution(grid):
    found = False

    # Check all spots for only one possibility
    for x in range(9):
        for y in range(9):
            if grid[9 * y + x] == -1:
                allowed = -1
                for n in range(9):
                    if is_allowed(grid, n, x, y):
                        if allowed == -1:
                            allowed = n
                        else:
                            allowed = -2
                            break
                if allowed != -2:
                    if allowed == -1:
                        return False
                    grid[9 * y + x] = allowed
                    found = True
    if found:
        return True

    # Check all columns for numbers that can only go in one cell
    for n in range(9):
        for x in range(9):
            allowed = -1
            for y in range(9):
                if grid[9 * y + x] == n:
                    allowed = -2
                    break
                if grid[9 * y + x] == -1:
                    if is_allowed(grid, n, x, y):
                        if allowed == -1:
                            allowed = y
                        else:
                            allowed = -2
                            break
            if allowed != -2:
                if allowed == -1:
                    return False
                grid[9 * allowed + x] = n
                found = True
    if found:
        return True

    # Check all rows for numbers that can only go in one cell
    for n in range(9):
        for y in range(9):
            allowed = -1
            for x in range(9):
                if grid[9 * y + x] == n:
                    allowed = -2
                    break
                if grid[9 * y + x] == -1:
                    if is_allowed(grid, n, x, y):
                        if allowed == -1:
                            allowed = x
                        else:
                            allowed = -2
                            break
            if allowed != -2:
                if allowed == -1:
                    return False
                grid[9 * y + allowed] = n
                found = True
    if found:
        return True

    # Check all boxes for numbers that can only go in one cell
    for n in range(9):
        for grid_x in range(0, 9, 3):
            for grid_y in range(0, 9, 3):
                allowed_x = -1
                allowed_y = -1
                for dx in range(3):
                    for dy in range(3):
                        if grid[9 * (grid_y + dy) + (grid_x + dx)] == n:
                            allowed_x = -2
                            break
                        if grid[9 * (grid_y + dy) + (grid_x + dx)] == -1:
                            if is_allowed(grid, n, grid_x + dx, grid_y + dy):
                                if allowed_x == -1:
                                    allowed_x = grid_x + dx
                                    allowed_y = grid_y + dy
                                else:
                                    allowed_x = -2
                                    break
                    else:
                        continue
                    break
                if allowed_x != -2:
                    if allowed_x == -1:
                        return False
                    grid[9 * allowed_y + allowed_x] = n
                    found = True
    if found:
        return True

    # Last resort, trial runs
    for nums_to_try in range(2, 10):
        for x in range(9):
            for y in range(9):
                valid_nums = []
                for n in range(9):
                    if is_allowed(grid, n, x, y):
                        valid_nums.append(n)
                        if len(valid_nums) > nums_to_try:
                            break
                if len(valid_nums) == nums_to_try:
                    for n in valid_nums:
                        grid2 = grid[:]
                        grid2[9 * y + x] = n
                        if try_solve(grid2):
                            for i in range(81):
                                grid[i] = grid2[i]
                            return True

    return False


def try_solve(grid):
    while not is_solved(grid):
        if not add_to_solution(grid):
            return False
    return True


solved_grid = grid[:]
if not try_solve(solved_grid):
    print("Impossible sudoku")
else:
    for y in range(9):
        for x in range(9):
            print(solved_grid[9 * y + x] + 1, " ", end="")
        print()