https://scammingthecodinginterview.com/ : Problem 002: Sudoku Solver

sudoku_solver.py

"""
Scamming the coding interview
"""


def is_valid(sudoku_grid, i, j):

    is_board_valid = check_the_grid(sudoku_grid, i, j) and \
                     check_row(sudoku_grid, i, j) and \
                     check_col(sudoku_grid, i, j)

    return is_board_valid


def check_the_grid(sudoku_grid, i, j):

    offset_x = int(i/3) * 3
    offset_y = int(j/3) * 3

    num = sudoku_grid[i][j]

    for row in range(offset_x, offset_x+3):
        for col in range(offset_y, offset_y+3):

            cell_value = sudoku_grid[row][col]

            if cell_value == num and not (i == row and j == col):
                return False
    return True


def check_row(sudoku_grid, i, j):

    num = sudoku_grid[i][j]

    for row in range(0, 9):

        if sudoku_grid[row][j] == num and not (row == i):
            return False

    return True


def check_col(sudoku_grid, i, j):
    num = sudoku_grid[i][j]

    for col in range(0, 9):

        if sudoku_grid[i][col] == num and not (col == j):
            return False

    return True


def sudoku_helper(sudoku_grid):

    status = True

    for i in range(0, 9):
        for j in range(0, 9):

            cell = sudoku_grid[i][j]

            if cell == 0:

                # this cell is not yet assigned
                # Try assigning it all the numbers and try if it leads to a valid configuration

                status = False

                for num in range(1, 10):

                    sudoku_grid[i][j] = num

                    if is_valid(sudoku_grid, i, j):
                        status = sudoku_helper(sudoku_grid)
                    if status:
                        break
                    else:
                        status = False

                if not status:
                    sudoku_grid[i][j] = 0
                    return False

    return status


if __name__ == '__main__':

    sg = [
        [3, 0, 6, 5, 0, 8, 4, 0, 0], 
        [5, 2, 0, 0, 0, 0, 0, 0, 0], 
        [0, 8, 7, 0, 0, 0, 0, 3, 1], 
        [0, 0, 3, 0, 1, 0, 0, 8, 0], 
        [9, 0, 0, 8, 6, 3, 0, 0, 5], 
        [0, 5, 0, 0, 9, 0, 6, 0, 0], 
        [1, 3, 0, 0, 0, 0, 2, 5, 0], 
        [0, 0, 0, 0, 0, 0, 0, 7, 4], 
        [0, 0, 5, 2, 0, 6, 3, 0, 0]
    ]

    sudoku_helper(sg)

    print(sg)