# 9x9 puzzle
puzzle = [5, 3, 0, 0, 7, 0, 0, 0, 0,
          6, 0, 0, 1, 9, 5, 0, 0, 0,
          0, 9, 8, 0, 0, 0, 0, 6, 0,
          8, 0, 0, 0, 6, 0, 0, 0, 3,
          4, 0, 0, 8, 0, 3, 0, 0, 1,
          7, 0, 0, 0, 2, 0, 0, 0, 6,
          0, 6, 0, 0, 0, 0, 2, 8, 0,
          0, 0, 0, 4, 1, 9, 0, 0, 5,
          0, 0, 0, 0, 8, 0, 0, 7, 9]

      
# retrieve rows
def extract_rows(puzzle):
    rows = []
    row = []
    for i in puzzle:
        row.append(i)
        if len(row) == 9:
            rows.append(row)
            row = []
    return rows
    
      
# retrieving values in columns     
def extract_cols(puzzle):
  cols = []
  for i in range(9):
    col = []
    for j in range(9):
      col.append(puzzle[j][i])
    cols.append(col)

  return cols


  
# Retrieves values of every sqaure 3x3 cells
# the formula j//3+(i//3)*3 calculates the value of the 3x3 grid from 0 to 8 
# depending on the column j and row i, starting top left and ending bottom right 
def get_squares(puzzle):
  sqs = [[], [], [], [], [], [], [], [], []]
  for i in range(9):
    for j in range(9):
      sqs[j//3+(i//3)*3].append(puzzle[i][j])
  return sqs



# finds locations of missing values by 3x3 square, row and column
def find_all_empty(puzzle):
  locs = {}
  for row in range(9):
    for col in range(9):
      if puzzle[row][col] == 0:
        # cell(square), row and column numbers
        locs[(col//3+(row//3)*3),row, col] = []
  
  return locs  

# missing values per Square of 3 x 3
def missing_valuesSQs(SQs):
    missSQs =[]
    allrow = [x for x in range(1,10)]
    for i in range(9):
        row = []
        for j in allrow:
            if j not in SQs[i]:
                row.append(j)
        missSQs.append(row)
    return missSQs
    
# Assign all possible values to each value missing:
# acording to missign numbers from 1-9 in 3x3 squares, rows and columns

def possible_values(empty_info, SQs, Rows, Cols, missSQs):
    empty = empty_info
    for key in empty.keys():
        for val in missSQs[key[0]]:
            if val not in SQs[key[0]] and val not in Rows[key[1]] and val not in Cols[key[2]]:
                empty[key].append(val) 
    return empty

# cells that have numbers with only one possible value are filled and 
# missing numbers in 3x3 square are updated 
def assign_single(puzzle, empty, missSQs):
    p1 = puzzle
    missSQs = missSQs
    for k in empty.keys():
        if len(empty[k]) == 1:
            #print(k, empty[k])
            p1[k[1]][k[2]] = empty[k][0]
            missSQs[k[0]].pop(missSQs[k[0]].index(empty[k][0]))
        

    return p1,  missSQs

def print_sudoku(sudoku):
    for row in sudoku:
        print(row)
    

# Solution


def solution(puzzle):
    Rows = extract_rows(puzzle)
    Cols = extract_cols(Rows)
    SQs = get_squares(Rows)
    missing = find_all_empty(Rows) 
    total_missing = len(missing)
    missSQs = missing_valuesSQs(SQs)
    possible_numbers = possible_values(missing, SQs, Rows, Cols, missSQs)

    print_sudoku(Rows)
    print("\n")
    counter = 0      

    #initial solution
    solution,  missSQs = assign_single(Rows, possible_numbers, missSQs)
    

    while len(possible_numbers) > 0:
        Rows = solution
        Cols = extract_cols(solution)
        SQs = get_squares(solution)
        missing = find_all_empty(solution) 
        left_missing = len(missing)
        possible_numbers = possible_values(missing, SQs, Rows, Cols, missSQs)
        counter += 1
        solution,  missSQs = assign_single(solution, possible_numbers, missSQs)
        print("iteration: ",counter, "\t",round(100 - left_missing*100/total_missing, 2), "% solved")
    
    print("\n")
    return solution


print_sudoku(solution(puzzle))


# 9x9 puzzle
puzzle = [5, 3, 0, 0, 7, 0, 0, 0, 0,
          6, 0, 0, 1, 9, 5, 0, 0, 0,
          0, 9, 8, 0, 0, 0, 0, 6, 0,
          8, 0, 0, 0, 6, 0, 0, 0, 3,
          4, 0, 0, 8, 0, 3, 0, 0, 1,
          7, 0, 0, 0, 2, 0, 0, 0, 6,
          0, 6, 0, 0, 0, 0, 2, 8, 0,
          0, 0, 0, 4, 1, 9, 0, 0, 5,
          0, 0, 0, 0, 8, 0, 0, 7, 9]

      
# retrieve rows
def extract_rows(puzzle):
    rows = []
    row = []
    for i in puzzle:
        row.append(i)
        if len(row) == 9:
            rows.append(row)
            row = []
    return rows
    
      
# retrieving values in columns     
def extract_cols(puzzle):
  cols = []
  for i in range(9):
    col = []
    for j in range(9):
      col.append(puzzle[j][i])
    cols.append(col)

  return cols


  
# Retrieves values of every sqaure 3x3 cells
# the formula j//3+(i//3)*3 calculates the value of the 3x3 grid from 0 to 8 
# depending on the column j and row i, starting top left and ending bottom right 
def get_squares(puzzle):
  sqs = [[], [], [], [], [], [], [], [], []]
  for i in range(9):
    for j in range(9):
      sqs[j//3+(i//3)*3].append(puzzle[i][j])
  return sqs



# finds locations of missing values by 3x3 square, row and column
def find_all_empty(puzzle):
  locs = {}
  for row in range(9):
    for col in range(9):
      if puzzle[row][col] == 0:
        # cell(square), row and column numbers
        locs[(col//3+(row//3)*3),row, col] = []
  
  return locs  

# missing values per Square of 3 x 3
def missing_valuesSQs(SQs):
    missSQs =[]
    allrow = [x for x in range(1,10)]
    for i in range(9):
        row = []
        for j in allrow:
            if j not in SQs[i]:
                row.append(j)
        missSQs.append(row)
    return missSQs
    
# Assign all possible values to each value missing:
# acording to missign numbers from 1-9 in 3x3 squares, rows and columns

def possible_values(empty_info, SQs, Rows, Cols, missSQs):
    empty = empty_info
    for key in empty.keys():
        for val in missSQs[key[0]]:
            if val not in SQs[key[0]] and val not in Rows[key[1]] and val not in Cols[key[2]]:
                empty[key].append(val) 
    return empty

# cells that have numbers with only one possible value are filled and 
# missing numbers in 3x3 square are updated 
def assign_single(puzzle, empty, missSQs):
    p1 = puzzle
    missSQs = missSQs
    for k in empty.keys():
        if len(empty[k]) == 1:
            #print(k, empty[k])
            p1[k[1]][k[2]] = empty[k][0]
            missSQs[k[0]].pop(missSQs[k[0]].index(empty[k][0]))
        

    return p1,  missSQs

def print_sudoku(sudoku):
    for row in sudoku:
        print(row)
    

# Solution


def solution(puzzle):
    Rows = extract_rows(puzzle)
    Cols = extract_cols(Rows)
    SQs = get_squares(Rows)
    missing = find_all_empty(Rows) 
    total_missing = len(missing)
    missSQs = missing_valuesSQs(SQs)
    possible_numbers = possible_values(missing, SQs, Rows, Cols, missSQs)

    print_sudoku(Rows)
    print("\n")
    counter = 0      

    #initial solution
    solution,  missSQs = assign_single(Rows, possible_numbers, missSQs)
    

    while len(possible_numbers) > 0:
        Rows = solution
        Cols = extract_cols(solution)
        SQs = get_squares(solution)
        missing = find_all_empty(solution) 
        left_missing = len(missing)
        possible_numbers = possible_values(missing, SQs, Rows, Cols, missSQs)
        counter += 1
        solution,  missSQs = assign_single(solution, possible_numbers, missSQs)
        print("iteration: ",counter, "\t",round(100 - left_missing*100/total_missing, 2), "% solved")
    
    print("\n")
    return solution


print_sudoku(solution(puzzle))


# 9x9 puzzle # retrieve rows # retrieving values in columns # Retrieves values of every sqaure 3x3 cells # the formula j//3+(i//3)*3 calculates the value of the 3x3 grid from 0 to 8 # depending on the column j and row i, starting top left and ending bottom right # finds locations of missing values by 3x3 square, row and column # cell(square), row and column numbers # missing values per Square of 3 x 3 # Assign all possible values to each value missing: # acording to missign numbers from 1-9 in 3x3 squares, rows and columns # cells that have numbers with only one possible value are filled and # missing numbers in 3x3 square are updated #print(k, empty[k]) # Solution #initial solution