sudoku_solver.py

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

def display_board(board):
    """Displays board in the human-readable format."""
    for i, row in enumerate(board):
        for j, elem in enumerate(row):
            spacing = 2 * ' ' if j % 3 == 2 else ' '
            print(elem, end=spacing)
        spacing = '\n' if i % 3 == 2 else ''
        print(spacing)

def get_list_from_square(board, row_index, column_index):
    """Returns list that contains all numbers in given square on sudoku board

    Args:
        board (list): sudoku board
        row_index (int): what is the row of the number we test
        column_index (int): what is the column of the number we test

    Returns:
        list: list of numbers in the proper square on sudoku board
    """
    vertical_square_index = row_index // 3
    horizontal_square_index = column_index // 3

    square_list = []
    for i in range(3*vertical_square_index, 3*vertical_square_index+3):
        for j in range(3*horizontal_square_index, 3*horizontal_square_index+3):
            square_list.append(board[i][j])

    return square_list

def get_column_from_board(board, column_index):
    """Returns list that is board's column.

    Args:
        board (list): sudoku list
        column_index (int): index of the column in sudoku board

    Returns:
        list: column in sudoku board
    """
    column = []
    for row in board:
        column.append(row[column_index])
    return column

def is_field_valid(board, row_index, column_index):
    """Tests whether inserted number is valid.

    Args:
        board (list): sudoku board
        row_index (int): what is the row of the number we test
        column_index (int): what is the column of the number we test

    Returns:
        bool: whether inserted number is valid, or not
    """

    # We check that the number in field is unique in whole row
    field = board[row_index][column_index]
    row = board[row_index]
    if row.count(field) != 1:
        return False

    # We check that the number in field is unique in whole column
    column = get_column_from_board(board, column_index)
    if column.count(field) != 1:
        return False

    # We check that the number in field is unique in whole 3x3
    square_list = get_list_from_square(board, row_index, column_index)
    if square_list.count(field) != 1:
        return False

    # Every test passed positively
    return True

def is_board_valid(board):
    """Tests whether board solution is valid

    Args:
        board (list): sudoku board

    Returns:
        bool: whether the solution is correct, or not
    """
    for i in range(81):
        row_index = i // 9
        column_index = i % 9
        if not is_field_valid(board, row_index, column_index):
            return False

        if board[row_index][column_index] not in range(1, 10):
            return False

    return True


def find_empty_field(board):
    for row_index, row in enumerate(board):
        if 0 in row:
            column_index = row.index(0)
            return row_index, column_index

def solve_sudoku(board):
    """Main solver function."""

    if is_board_valid(board):
        display_board(board=board)
        exit(0)

    # 1. We search for the empty field
    row_index, column_index = find_empty_field(board)

    # 2. We try to insert different numbers
    for j in range(1, 10):
        board[row_index][column_index] = j
        if is_field_valid(board, row_index, column_index):
            solve_sudoku(board=board)
        board[row_index][column_index] = 0


# TESTS
def test_getting_list_from_square():
    assert [7,8,0,6,0,0,0,0,0] == get_list_from_square(BOARD, 0, 0)
    assert [4,0,0,0,7,5,6,0,1] == get_list_from_square(BOARD, 2, 4)
    assert [0,4,0,0,5,0,0,6,0] == get_list_from_square(BOARD, 5, 3)
    assert [0,1,2,4,0,0,0,0,7] == get_list_from_square(BOARD, 7, 8)
    assert [3,0,0,0,0,7,2,0,6] == get_list_from_square(BOARD, 7, 4)
    assert [2,6,0,9,3,0,0,0,5] == get_list_from_square(BOARD, 5, 8)
    assert [2,6,0,9,3,0,0,0,5] == get_list_from_square(BOARD, 3, 7)

def test_getting_column_from_board():
    assert [7,6,0,0,0,9,0,1,0] == get_column_from_board(BOARD, 0)
    assert [4,0,6,0,0,0,3,0,2] == get_column_from_board(BOARD, 3)
    assert [0,5,1,0,0,0,0,7,6] == get_column_from_board(BOARD, 5)
    assert [2,0,7,6,3,0,1,0,0] == get_column_from_board(BOARD, 7)


if __name__ == '__main__':
    test_getting_list_from_square()
    test_getting_column_from_board()
    solve_sudoku(BOARD)