sudoku_solve.py

def search(grid_dict):

	# try to solve the board
    grid_dict = run_episode(grid_dict)
    

    if grid_dict is False:

    	# it means the current configuration of the board is unsolvable
    	# this happens when any of the boxes have no possible value to fix
        return False
    

    if all(len(v) == 1 for k,v in grid_dict.items()): 

    	# it means the board is solved
        return grid_dict


    # ==========================================================================================
    # The code above this line is to stop recursion (BASE CASE) and
    # The code below this line is to continue recursion (RECURSIVE CASE)
    # ==========================================================================================
    
    # Choose one of the unfilled squares with the fewest possibilities
    length,k = min((len(val), key) for key,val in grid_dict.items() if len(val) > 1)
    # print(k, length)
    

    # Now use recurrence to solve each one of the resulting sudokus, and 
    for digit in grid_dict[k]:
        new_sudoku = dict(list(grid_dict.items()))

        # fix the value of the box
        new_sudoku[k] = digit

        # try to solve the new configuration of the board
        try_to_solve_new_config = search(new_sudoku)

        if try_to_solve_new_config: 			# if the board is solved
            return try_to_solve_new_config		# return the solved board

        # if the board is not solved yet (got stuck again in the new configuration)
        # fix another digit and try again (thats what the loop is for)
        # keep fixing digits and try to solve until that configuration is either impossibe to solve
        # or it is solved