Easy-Medium Sudoku solver written in Python - No recursion/ brute force

Question

I'm very new to software developing, I wrote this Sudoku solver in Python, it's not the best approach ever I know and that is I guess because I started taking courses in Python and programming a month ago, of course there are much much better versions of Sudoku solvers out there and maybe written in less amount of code, however this code is fast enough and is able to solve up to some hard Sudoku puzzles. However here's the code, I want your feedback/suggestions if there is a way to make it shorter/more efficient ... I'm looking forward to improve this code in the future in order that it supports brute forcing as well but for now check it and give me your feedback. How's that for a newbie software developer?

import operator
from time import time
import copy
# Given an incomplete Sudoku configuration in terms of a 9 x 9  2-D 
# square matrix, the task is to solve it assuming
# there is only one uniques solution.
# * * This code is not designed to solve hard Sudoku puzzles: it does 
# not contain a brute force algorithm.


def coordinate():
    """Makes a coordinate dictionary by manually typing the 
coordinates"""
    dic = {}
    ind_list =[(x, y) for x in range(9) for y in range(9)]
    for i in ind_list:
        temp = []
        cd = input("Enter block coordinates: ")
        for j in cd:
            temp.append(int(j))
        dic[i] = temp
    print(dic)


# I made this to make a dictionary of coordinates
# for further use later (I know this is not the best
# approach ever)                                                                 
# proper use:
# for columns --> returns the pair of coordinates
# for rows    --> returns the reversed pair


def coordinates():
    """Block coordinates to column or row"""
    coordinates = \
      {(0, 0): [0, 0], (0, 1): [0, 3], (0, 2): [0, 6],
       (0, 3): [3, 0], (0, 4): [3, 3], (0, 5): [3, 6],
       (0, 6): [6, 0], (0, 7): [6, 3], (0, 8): [6, 6],
       (1, 0): [0, 1], (1, 1): [0, 4], (1, 2): [0, 7],
       (1, 3): [3, 1], (1, 4): [3, 4], (1, 5): [3, 7],
       (1, 6): [6, 1], (1, 7): [6, 4], (1, 8): [6, 7],
       (2, 0): [0, 2], (2, 1): [0, 5], (2, 2): [0, 8],
       (2, 3): [3, 2], (2, 4): [3, 5], (2, 5): [3, 8],
       (2, 6): [6, 2], (2, 7): [6, 5], (2, 8): [6, 8],
       (3, 0): [1, 0], (3, 1): [1, 3], (3, 2): [1, 6],
       (3, 3): [4, 0], (3, 4): [4, 3], (3, 5): [4, 6],
       (3, 6): [7, 0], (3, 7): [7, 3], (3, 8): [7, 6],
       (4, 0): [1, 1], (4, 1): [1, 4], (4, 2): [1, 7],
       (4, 3): [4, 1], (4, 4): [4, 4], (4, 5): [4, 7],       
       (4, 6): [7, 1], (4, 7): [7, 4], (4, 8): [7, 7],   
       (5, 0): [1, 2], (5, 1): [1, 5], (5, 2): [1, 8],                                                                     
       (5, 3): [4, 2], (5, 4): [4, 5], (5, 5): [4, 8],      
       (5, 6): [7, 2], (5, 7): [7, 5], (5, 8): [7, 8],       
       (6, 0): [2, 0], (6, 1): [2, 3], (6, 2): [2, 6],       
       (6, 3): [5, 0], (6, 4): [5, 3], (6, 5): [5, 6],
       (6, 6): [8, 0], (6, 7): [8, 3], (6, 8): [8, 6],
       (7, 0): [2, 1], (7, 1): [2, 4], (7, 2): [2, 7],
       (7, 3): [5, 1], (7, 4): [5, 4], (7, 5): [5, 7],
       (7, 6): [8, 1], (7, 7): [8, 4], (7, 8): [8, 7],
       (8, 0): [2, 2], (8, 1): [2, 5], (8, 2): [2, 8],
       (8, 3): [5, 2], (8, 4): [5, 5], (8, 5): [5, 8],
       (8, 6): [8, 2], (8, 7): [8, 5], (8, 8): [8, 8]}
    return coordinates

# To enter the Sudoku puzzle to solve
# Enter puzzle blocks separately (0 for empty)
# ex: 012056090


def test_list_build(n=9):
    """builds a list of lists(each block is a list)
    default size (9 * 9)
    returns a list of the whole puzzle"""
    puzzle_blocks = []
    for i in range(n):
        temp = []
        block = input("Enter block; number or 0 for empty slots: ")
        for j in block:
            temp.append(int(j))
        puzzle_blocks.append(temp)
    return puzzle_blocks

# for further use and construction of a list of columns/rows

def get_block_row(puzzle, row_number, block_number):
    """returns a list of block row (1, 2 or 3)
       assumes row number is not zero indexed"""
    if row_number == 1:
        return puzzle[block_number][:3]
    if row_number == 2:
        return puzzle[block_number][3:6]                
    if row_number == 3:
        return puzzle[block_number][6:]


def get_row(puzzle, row_number):
    """takes puzzle, row number and returns the full row"""
    # ex: given row number, appends slices from
    # each block containing the slice, joins slices
    # and returns the row

    puzzle_copy = copy.deepcopy(puzzle)
    temporary_row = []
    row = []
    if row_number in range(4, 7):
        del puzzle_copy[:3]
        row_number = row_number - 3
    if row_number in range(7, 10):
        del puzzle_copy[:6]
        row_number = row_number - 6
    if row_number == 1:
        for i in range(3):
            temporary_row.append(get_block_row(puzzle_copy, 1, i))
    if row_number == 2:
        for i in range(3):
            temporary_row.append(get_block_row(puzzle_copy, 2, i))      
    if row_number == 3:                                                 
        for i in range(3):                                              
            temporary_row.append(get_block_row(puzzle_copy, 3, i))
    for slice in temporary_row:
        for number in slice:
            row.append(number)
    return row   

def get_all_rows(puzzle):
    """returns a list of lists(rows)"""
    all_rows = []
    for i in range(1, 10):
        all_rows.append(get_row(puzzle, i))
    return all_rows


def get_column(puzzle, column_number):
    """extracts a column from all rows"""
    rows = get_all_rows(puzzle)
    columns = []
    for row in rows:
        columns.append(row[column_number - 1])
    return columns


def get_all_columns(puzzle):
    """returns a list of lists(columns)"""
    all_columns = []
    for i in range(1, 10):
        all_columns.append(get_column(puzzle, i))
    return all_columns


def print_puzzle_with_zeros(puzzle):
    """given an empty or a full puzzle, prints the puzzle with zeros for 
    empty slots"""
    all_rows = get_all_rows(puzzle)
    count = 0
    for i in all_rows:
        count2 = 0
        for j in i:
            print(j, end=' ')
            count2 += 1
            if count2 % 3 == 0:
                print(' ', end='')
        count += 1
        if count % 3 == 0:
            print()
        print()

# The following function checks if numbers in range(1, 9) inclusively 
# are in all columns and rows.

def is_solved(puzzle):
    """checks the puzzle, if solved, returns True, else returns False"""
    all_rows = get_all_rows(puzzle)
    all_columns = get_all_columns(puzzle)
    check = True
    for i in range(1, 10):
        for row in all_rows:
            if i not in row:
                check = False             
                return check
    for i in range(1, 10):
        for column in all_columns:
            if i not in column:
                check = False
                return check
    return check


# The following function returns a sorted list to deal with the least 
# empty blocks first because they're easier to solve first.

def get_empty_indexes_blocks(puzzle):
    """takes puzzle, returns list containing sorted enumerated blocks 
    from least empty to most empty, length and
    a sublist of empty block indexes"""
    empty_block_slots = []
    for block in puzzle:
        temp = []
        for index, number in enumerate(block):  
            if number == 0:                     
                temp.append(index)
        empty_block_slots.append(temp)
    numbered = list(enumerate(empty_block_slots))
    final = []
    for block_index, empty_indexes in numbered:
        final.append((block_index, len(empty_indexes), empty_indexes))
    return sorted(final, key=operator.itemgetter(1))

def get_missing_numbers_blocks(puzzle):
    """works the same as get_empty_indexes, difference is it contains a\ 
    sublist of missing numbers in the block"""
    all_blocks = []
    for block in puzzle:
        temp = []
        for number in range(1, 10):
            if number not in block:
                temp.append(number)
        all_blocks.append(temp)
    numbered = list(enumerate(all_blocks))
    final = []
    for block_index, missing_numbers in numbered:
        final.append((block_index, len(missing_numbers),\ 
        missing_numbers))
    return sorted(final, key=operator.itemgetter(1))


# The following function uses coordinates pre-defined above

def col_row_to_block(position, index_pos, index_in):
    """takes 'c' for column and 'r' for row, column or row index, next 
    index and converts to block coordinates"""
    coordinate_index = coordinates()                
    if position == 'c':
        return coordinate_index[index_pos, index_in]
    elif position == 'r':
        return coordinate_index[index_in, index_pos]


# This function is made to get block indexes for future use to be able
# to edit an empty block slot using list assignment.


def block_index_to_col_or_row(position, block_index, index):
    """works same as col_row_to_block but converts from columns/rows to 
    block indexes"""
    dic = coordinates()
    for coordinates1, coordinates2 in dic.items():
        if position == 'c':
            if coordinates2 == [block_index, index]:
                return coordinates1                      
        if position == 'r':
            if coordinates2 == [block_index, index]:
                return tuple(reversed(coordinates1))


def possible_missing_numbers(puzzle):
    """contains 3 main sections:
       1. Solving by blocks
       2. Solving by rows
       3. Solving by columns
       returns a list of possible block coordinates and their missing\ 
       numbers"""
    # The following 'checker index' is meant to return indexes to check 
    # for a certain number
    # ex: if number not in column 1 ... where to check? --> check      
    # columns 0 & 2
    # same goes for rows
    checker_index = {0: (1, 2), 1: (0, 2), 2: (0, 1), 3: (4, 5), 4: (3,\ 
    5), 5: (3, 4), 6: (7, 8), 7: (6, 8), 8: (6, 7)}

    all_cols = get_all_columns(puzzle)                     
    all_rws = get_all_rows(puzzle)                         
    missing_blocks = get_missing_numbers_blocks(puzzle)    
    empty_blocks = get_empty_indexes_blocks(puzzle)        
    empty_block_indexes_missing_numbers_in_block = []
    empty_block_indexes_missing_numbers_in_block2 = []
    empty_block_indexes_missing_numbers_in_block3 = []
    possible_per_block_row = {x: [] for x in range(1, 10)} 
    possible_per_block_col = {x: [] for x in range(1, 10)} 
    possible = []
    extra_work = []     
    to_col_row = {}
    to_row_col = {}
    unify = []
    unify2 = []         
    unify3 = []         
    unify4 = []
    location_possible = {} 

    # The previous variables contain/ are supposed to contain the       
    # following:
    # list of all columns
    # list of all rows
    # list of missing numbers in each block
    # list of empty indexes in each block
    # possible per row: number and its possible empty locations
    # possible per column : number and its possible empty locations
    # extra_work is meant to contain unique locations per block
    # the 4 unify empty lists are made to contain missing numbers and   
    # unique locations.
    # ex: if a number is missing in a column or a row and has only one  
    # position in the column/row
    # the end result, a dictionary containing coordinates(empty slots)  
    # as keys and missing nums.


    # 1. Solving by blocks
    for block_index1, length1, empty_indexes in empty_blocks:
        for block_index2, length2, missing_numbers in missing_blocks:
            empty_block_indexes_missing_numbers_in_block.append\ 
            ((block_index1, empty_indexes, missing_numbers))

    for block_index, empty_indexes, missing_numbers in\ 
        empty_block_indexes_missing_numbers_in_block:
        for empty_index in empty_indexes:
            for missing_number in missing_numbers:
                empty_block_indexes_missing_numbers_in_block2.append\ 
                ((block_index, empty_index, missing_number))

    for item in empty_block_indexes_missing_numbers_in_block2:
        col_coord = block_index_to_col_or_row('c', item[0], item[1])
        row_coord = block_index_to_col_or_row('r', item[0], item[1])
        empty_block_indexes_missing_numbers_in_block3.append((item,\ 
    col_coord[0], row_coord[0]))
    for item in empty_block_indexes_missing_numbers_in_block3:
        if item[0][2] not in puzzle[item[0][0]] and item[0][2] not in\ 
        all_cols[item[1]] and item[0][2] \
        not in all_rws[item[2]] and item not in possible:
            possible.append(item)
        if item[0][2] not in puzzle[item[0][0]]:
            cols_to_check = checker_index[item[1]]
            rows_to_check = checker_index[item[2]]
            if item[0][2] in all_cols[cols_to_check[0]] and item[0][2]\ 
            in all_cols[cols_to_check[1]]\
            and item[0][2] in all_rws[rows_to_check[0]] and item[0][2]\ 
            in all_rws[rows_to_check[1]]:
                extra_item =(item[0][2], item[0][0], item[0][1])
                if extra_item not in extra_work:
                    extra_work.append(extra_item)
    for item in possible:
        location_possible[(item[0][0], item[0][1])] = []
    for location, possible_list in location_possible.items():
        for item in possible:
            if (item[0][0], item[0][1]) == location:
                location_possible[location].append(item[0][2])
    for location, possible_list in location_possible.items():
        for item in extra_work:
            if (item[1], item[2]) == location:
                del location_possible[location]
                location_possible[location] = [item[0]]
    # 2. Solving by rows:
    for location, possible_list in location_possible.items():
        col_row = block_index_to_col_or_row('c', location[0],\ 
        location[1])
        row_col = tuple(reversed(col_row))
        to_col_row[col_row] = possible_list
        to_row_col[row_col] = possible_list
    for coords, list_possible in to_row_col.items():
        for missing_number in list_possible:
            block_coordinates = col_row_to_block('r', coords[0],\ 
            coords[1])
            other_rows = checker_index[coords[0]]
            if missing_number in all_rws[other_rows[0]] and\ 
               missing_number in all_rws[other_rows[1]] and\ 
               missing_number\
               not in all_cols[coords[1]] and missing_number not in\ 
               puzzle[block_coordinates[0]] \
               and missing_number not in all_rws[coords[0]]:
                   possible_per_block_row[missing_number].append\ 
                   ((block_coordinates[0], block_coordinates[1]))
    for num, possible_list in possible_per_block_row.items():
        for i in range(1, 10):
            for item in possible_list:
                if item[0] == i:
                    unify.append((num, item[0], item[1]))
    for item1 in unify:
        count = 0
        for item2 in unify:
            if (item1[0], item1[1]) == (item2[0], item2[1]):
                count += 1
        if count == 1:
            unify2.append(item1)
    for item in location_possible:
        for item2 in unify2:
            if (item2[1], item2[2]) == item:
                location_possible[item].clear()
                location_possible[item].append(item2[0])

    # 3. Solving by columns
    for coords, list_possible in to_col_row.items():
        for missing_number in list_possible:
            block_coordinates = col_row_to_block('c', coords[0],\ 
            coords[1])
            other_cols = checker_index[coords[0]]
            if missing_number in all_cols[other_cols[0]] and\ 
               missing_number in all_cols[other_cols[1]]\
               and missing_number not in puzzle[block_coordinates[0]]\ 
               and missing_number not in all_cols[coords[0]]\
               and missing_number not in all_rws[coords[1]]:
               possible_per_block_col[missing_number].append\ 
               ((block_coordinates[0], block_coordinates[1]))

    for num, possible_list in possible_per_block_col.items():
        for i in range(1, 10):
            for item in possible_list:
                if item[0] == i:
                    unify3.append((num, item[0], item[1]))
    for item1 in unify3:
        count = 0
        for item2 in unify3:
            if (item1[0], item1[1]) == (item2[0], item2[1]):
                count += 1
        if count == 1:
            unify4.append(item1)
    for item in location_possible:
        for item2 in unify4:
            if (item2[1], item2[2]) == item:
                location_possible[item].clear()
                location_possible[item].append(item2[0])
    return location_possible



def function_test(puzzle):
    """tests for predefined functions"""
    rows = get_all_rows(puzzle)
    columns = get_all_columns(puzzle)
    blocks = puzzle[:]
    empty_block_indexes = get_empty_indexes_blocks(puzzle)
    missing_blocks = get_missing_numbers_blocks(puzzle)
    print('rows:')
    print(rows)
    print()
    print('columns:')
    print(columns)
    print()
    print('blocks:')
    print(blocks)
    print()
    print('empty block indexes (sorted by length):')
    print(empty_block_indexes)
    print()
    print('missing numbers in blocks (sorted by length):')
    print(missing_blocks)
    print()
    print('Block location/Possible numbers')
    print(possible_missing_numbers(puzzle))


# The following function solves the puzzle using records to keep track
# of the length of possible locations for missing numbers' list
# If the length is constant for 2 consecutive iterations, then the 
# algorithm does not support the level of difficulty or the puzzle is
# wrongly entered
# And in that case the most up to date version of the solved puzzle is 
# returned with a message indicating this.
# If the puzzle is solved, it prints the puzzle using the predefined 
# function for printing the puzzles and returns a list of lists (the 
# solved version


def solve(puzzle):
    """solves the puzzle"""
    record = []                
    check_record = []
    puzzle_copy = copy.deepcopy(puzzle)
    print('Initial Puzzle:')
    print_puzzle_with_zeros(puzzle_copy)
    count = 0
    while not is_solved(puzzle_copy):
    # uncomment the following 3 lines if you want to see progression
    #   count += 1
    #   print(count)
    #   print_puzzle_with_zeros(puzzle_copy)        
        possible = possible_missing_numbers(puzzle_copy)
        record.append(len(possible))
        if record[-1] not in check_record:
            check_record.append(record.pop())
        else:
            print('initial:')
            print_puzzle_with_zeros(puzzle)
            print('Solved until: ')
            print()
            print_puzzle_with_zeros(puzzle_copy)
            print('Maybe the puzzle is incorrect or unsupported by this\ 
            kind of algorithm')
            return puzzle_copy
        for item1, item2 in possible.items():
            if len(item2) == 1 and puzzle_copy[item1[0]][item1[1]] == 0:
                puzzle_copy[item1[0]][item1[1]] = item2[0]
    if is_solved(puzzle_copy):
        print('Solved!')
        print_puzzle_with_zeros(puzzle_copy)
        return puzzle_copy


if __name__ == '__main__':

    # You can test with this Sudoku puzzle or enter one yourself

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

    # If you want to test another Sudoku puzzle uncomment 'test another'
    # and set 'p' in solve() to 'test_another'
    # Then you'll be prompted to enter the puzzle block, enter numbers
    # without spaces and enter 0 for empty slots

    # test_another = test_list_build()
    time1 = time()
    solve(p)
    time2 = time()
    print('%s seconds.' % (time2 - time1))

Answer 1

This is a lot of code so it's hard to prioritise which sections to review, so I'll do some fairly general stuff which is short and easy, then go a little more into the overall design. As a result, this won't be an exhaustive review.

• Follow PEP8 unless your employer has certain internal rules. Even then, try to follow standard style and only deviate when required. PEP8 is the standard for Python and makes your code more readable.

• print() takes a couple of arguments, one being end. The default is to end with a new line, end=\n but you can change this to no new line end='' or as many new lines as you want, end='\n\n'. You can also override the default behaviour for the whole file using functools.partial:

from functools import partial

print = partial(print, end='\n\n'

You could also use f-strings to tidy up a lot of the printing. In function_test() for example, the printing should be more like:

print(f'rows: {rows}')

• Never use except: pass. Even when you're logging exceptions you'll want to use except Exception: log(). Catching all exceptions will mean issues go completely unnoticed; it also catches KeyboardInterrupt and SystemExit, making it annoying to exit the program. Be specific about what exceptions you're catching.

• I'd write a decorator for timing, it will be very useful and transferrable. You can start with something bare-bones like the following, and expand as necessary for logging etc:

def timer(func):
    @wraps(func)
    def wrapper(*args, **kwargs):

        t1 = time()
        result = func(*args, **kwargs)
        t2 = time() - t1

        print(f'{func.__qualname__} ran in: {t2} seconds.')

        return result
    return wrapper

• If you're checking lots of required conditions, avoid using huge blocks of and and or. Use any() and all() with nice paragraphing where necessary.

• possible_missing_numbers() is very large and should be split up.

• Functions should have a "single" clear purpose and be explained with a docstring. (single is in quotes because this is a bit of a loose term. Generally, you will get a feel for what is an appropriately-sized function. Up to about 20 lines is a decent rule for Python.)

• Don't use built in names for variables (index and slice, for example). Your naming apart from that is sometimes OK but you use a lot of ambiguous names, or the same name but with a number on the end.

• You also create many more variables than necessary. For example is_solved() does not need the check variable at all. Just return True or False as and when necessary.

• Throughout most of your code you've appended to empty lists. This is often a sign you should be using generators instead. Rewriting with generators would also help you get a better feel for the length of a function, as you'll need to make functions for the generator to be called.

• You make heavy use of the \ to split lines. This indicates you're cramming too much logic into one line. It is also more conventional in Python to split lines by using parentheses.

• A lot of code could be vastly shortened (and made clearer) by using list/dict comprehensions and generator expressions. For example, get_column could become a nice one-liner:

def get_column(puzzle, column_number):
    """extracts a column from all rows"""
    return [row[column_number - 1] for row in get_all_rows(puzzle)]

• You really need more comments. Docstrings should broadly explain what functions do, then comments should explain the specifics. These comments should be immediately above the relevant code, or in-line if very short.

As for some design choices:

• I'm not sure why you've used defined coordinates. Lists are ordered and I think storing 9 list of lists of length 9 would be far better than what you have. You can just access items by their index.

• There are many named sudoku solving algorithms. These have names that are recognisable to solvers (X-wings etc). If you're not brute-forcing, using the standard naming to explain what you're doing will help readers of your code. Even if the implementations are your own, the algorithms should be recognisable.

• You could really do with a better way of inputting tests. Perhaps a file reader would be a good idea? Maybe there's an online gui you can use to generate one if you don't fancy writing your own.

• It might be a good idea to split this code into two classes. One that describes the structure of a Sudoku and has some basic transformations like reflections, swapping rows or columns etc. Then a second class which contains the actual solving logic. You can then make tests which are instances of the first class and are solved with the second. This creates some structure to your code and makes it clearer how things are working.

• I think because you have written so much code with so few functions, you maybe don't realise how much is repeated. As you separate out your code you should notice that a lot of it can be reused rather than rewritten. get_empty_indexes_blocks() and get_missing_numbers_blocks() for example are extremely similar.

Answer 2

I think your code is very long. To solve Sudoku by computer, here is what you want to do:

1. Is there anything immediately obvious (e.g: can only one number be entered into any given square)? If yes, enter it.
2. If not, list all the numbers that do fit into a given square in a separate array.
3. If there are any unique elements in this list compared to its surrounding 3*3 grid, row or column then apply it (e.g. if a square could contain the numbers [1, 3, 6] and the number 6 cannot be held by any square in the same 3*3 box, row or column, then enter 6 to that square.)
4. Repeat this process until the board is full.

Of course, as you point out, this will only work to an extent. This is not a recursive solution and so there will reach a point where no further progress is made on very challenging boards.

My code automatically terminates after 5 seconds to stop it entering a vicious loop

I would also point out that you have used deep copy. Although it seems this is only called once, deep copy is very slow indeed. If you want to copy an array, using something like Numpy is better. The time differences are significant.

You have also got a function to check if 1-9 are present in every row/column/square. A much better solution would be be to just check for 0 in the entire array. If you find any 0 anywhere on the board you know it is unsolved and can continue immediately to trying to solve it. This works because you should only replace 0 when you have a definite number to replace it.

Of course, if you say after 1 or 2 seconds of solving this way that you then want to recursively solve the rest of the board, it will be much faster!

import itertools
import time


def board_solved(board):
    for row in range(0, 9):
        for column in range(0, 9):
            if board[row][column] == 0:
                return False
    return True


def in_surrounding(row, column, target, board):
    dictonary_get = {0: (0, 1, 2),
                     1: (0, 1, 2),
                     2: (0, 1, 2),
                     3: (3, 4, 5),
                     4: (3, 4, 5),
                     5: (3, 4, 5),
                     6: (6, 7, 8),
                     7: (6, 7, 8),
                     8: (6, 7, 8)}
    row_set = dictonary_get[row]
    column_set = dictonary_get[column]
    for row_item in row_set:
        for column_item in column_set:
            if row_item == row and column_item == column: continue
            try:
                if (board[row_item][column_item] == target) or (target in board[row_item][column_item]):
                    return True
            except:
                pass
    return False


def solve_multiple(board, array_poss):
    ranges = [i for i in range(9)]
    for row, column in itertools.product(ranges, ranges):
        list_poss = array_poss[row][column]
        if not list_poss:
            continue
        for target in list_poss:
            # Is an element unique in its 3*3 square
            if not in_surrounding(row, column, target, array_poss):
                board[row][column] = target
                break
            # Obtain set_row
            set_row = set()
            for index, item in enumerate(array_poss[row]):
                if index == column: continue
                if isinstance(item, int):
                    set_row.add(item)
                else:
                    for element in item:
                        set_row.add(element)
            # Obtain set_columns
            set_columns = set()
            list_column = []
            for row_pointer in range(9):
                list_column.append(array_poss[row_pointer][column])
            for index, item in enumerate(list_column):
                if index == row: continue
                if isinstance(item, int):
                    set_columns.add(item)
                else:
                    for element in item:
                        set_columns.add(element)
            # If unique, add to board
            if not target in set_row or not target in set_columns:
                board[row][column] = target
                break

    return board


def solve_board(board):
    ranges = [i for i in range(9)]
    start_time = time.time()
    while not board_solved(board):
        if time.time() - start_time > 5:
            print("This board is too hard or not possible. This is the progress the program has made on the board")
            return board
        array_poss = [[0 for i in range(9)] for j in range(9)]  # Build an array of possible numbers in a given square
        any_changes = 0
        for row, column in itertools.product(ranges, ranges):
            list_valid = []
            if not board[row][column]:
                for try_number in range(1, 10):
                    if try_number in board[row]:  # If try_number is present in the row, move to next number
                        continue
                    if try_number in [board[i][column] for i in
                                      range(0, 9)]:  # If try_number is present in the column, move to next number
                        continue
                    if in_surrounding(row, column, try_number,
                                      board):  # If try_number is present in the surrounding 3*3 grid, move to next number
                        continue
                    list_valid.append(try_number)  # Else add the number to list_valid
                # After trying all numbers, if the length of list_valid is 1, make the change
                if len(list_valid) == 1:
                    board[row][column] = list_valid[0]
                    any_changes = 1
                else:
                    # Otherwise place list_valid (which is the list of hidden pairs) in the 9*9 grid
                    array_poss[row][column] = list_valid
        if any_changes == 0:
            board = solve_multiple(board, array_poss)
    return board


if __name__ == "__main__":
    board = [[0, 0, 0, 3, 0, 2, 1, 0, 0],
             [0, 9, 0, 0, 0, 5, 0, 8, 0],
             [0, 0, 0, 8, 9, 0, 7, 0, 0],
             [0, 0, 4, 0, 0, 1, 5, 0, 0],
             [0, 6, 0, 0, 4, 0, 0, 7, 0],
             [0, 0, 2, 5, 0, 0, 9, 0, 0],
             [0, 0, 5, 0, 8, 7, 0, 0, 0],
             [0, 1, 0, 6, 0, 0, 0, 2, 0],
             [0, 0, 7, 1, 0, 4, 0, 0, 0]]

    solved_board = solve_board(board)
    print(*(row for row in solved_board), sep="\n")