Sudoku Solver using rules of Sudoku and backtracking

Question

This code tries to solve the sudoku board using the rules of sudoku. When it does not make progress in solving, it assumes a cell value and tries again. Please review my code and help me understand how I can make it better.

import math
import copy
import sys
# GLOBALS
reccursion_depth = 0
dead_end_counter = 0
assumption_counter = 0
solution_counter = 0
# OPTIONS
PRINT_STEPS = False
PRINT_STEP_BOARD = False
PRINT_ASSUMPTION = False
ASSUME_LOWEST_FIRST = True
# When True, assumptions will be made on cells with smallest possible choices, else Left2Right-Top2Down.
FIRST_SOLUTION_ONLY = False
def initiate_board(problem):
 board_pos = [[[i for i in range(1,10)] for i in range(9)] for i in range(9)]
 for i,row in enumerate(problem):
 for j,cell in enumerate(row):
 if cell > 0:
 board_pos[i][j] = [cell]
 return board_pos
def remove_invalid(board_pos):
 if PRINT_STEPS: print("Removing Invalid Values..")
 org_length = board_length(board_pos) #Used to check if Rule based algorithm made progress.
 for i,row in enumerate(board_pos):
 for j,cell in enumerate(row):
 if len(cell) == 1:
 for e in range(9):
 # 1. Remove from Row
 if e != j:
 try:
 board_pos[i][e].remove(cell[0])
 if len(board_pos[i][e]) == 0:
 if PRINT_STEPS: print(f"ROW CHECK: Board is invalid at position ({i},{j})")
 return False, False, board_pos
 valid_col = False
 for counter_col in range(9):
 if cell[0] in board_pos[counter_col][e]:
 valid_col = True
 break
 if not valid_col:
 if PRINT_STEPS: print(f'COLUMN CHECK: Value {cell[0]} not present in column {e}! ')
 return False, False, board_pos
 except ValueError:
 pass
 # 2. Remove from Column
 if e != i:
 try:
 board_pos[e][j].remove(cell[0])
 if len(board_pos[e][j]) == 0:
 if PRINT_STEPS: print(f"COLUMN CHECK: Board is invalid at position ({e},{j})")
 return False, False, board_pos
 valid_row = False
 for counter_row in range(9):
 if cell[0] in board_pos[e][counter_row]:
 valid_row = True
 break
 if not valid_row:
 if PRINT_STEPS: print(f'ROW CHECK: Value {cell[0]} not present in row {e}! ')
 return False, False, board_pos
 except ValueError:
 pass
 # 3. Remove from Sector
 sector_row = math.floor((i) / 3)
 sector_col = math.floor((j) / 3)
 #print(sector_row, sector_col, ':',cell[0])
 for i_sec in range(sector_row*3, (sector_row+1)*3):
 for j_sec in range(sector_col*3, (sector_col+1)*3):
 if i != i_sec and j !=j_sec:
 try:
 board_pos[i_sec][j_sec].remove(cell[0])
 if len(board_pos[i_sec][j_sec]) == 0:
 if PRINT_STEPS: print(f"SECTOR CHECK: Board is invalid at position ({i_sec},{j_sec})")
 return False, False, board_pos
 # Add check here to ensure every number is an option for the Sector. Missing check will eventually lead to dead end anyways.
 except ValueError:
 pass
 return True, (org_length == board_length(board_pos)), board_pos
def board_length(board_pos):
 total_length = 0
 for i,row in enumerate(board_pos):
 for j,cell in enumerate(row): 
 total_length +=len(cell)
 return total_length
 
def print_board(board_pos):
 if not isinstance(board_pos[0][0], int): print(f'####### SOLUTION NUMBER {solution_counter} #######')
 for row in board_pos:
 print(row)
 if not isinstance(board_pos[0][0], int):
 print(f"Current Board Length: {board_length(board_pos)}")
 print(f"Current Reccursion Depth: {reccursion_depth}")
 print(f"Current Number of Dead Ends: {dead_end_counter}")
 print(f"Number of assumptions made: {assumption_counter}")
def is_solved(board_pos):
 for row in board_pos:
 for cell in row:
 if len(cell) != 1: 
 return False 
 return True
def get_next_assume_candidate(board_pos):
 assume_list = []
 possibilities = 1
 for i,row in enumerate(board_pos):
 for j,cell in enumerate(row): 
 if len(cell) > 1:
 assume_list.append([i,j,len(cell)])
 possibilities = possibilities * len(cell)
 sorted_assume = sorted(assume_list, key = lambda x: x[2]) 
 if ASSUME_LOWEST_FIRST:
 return (sorted_assume[0], possibilities)
 else:
 return (assume_list[0], possibilities)
 
def solve_sudoku(board_pos):
 global reccursion_depth
 global dead_end_counter
 global assumption_counter
 global solution_counter
 
 reccursion_depth += 1
 if PRINT_STEPS: print('reccursion depth :', reccursion_depth)
 while not is_solved(board_pos):
 if PRINT_STEPS: print('Trying to Solve by applying rules of Sudoku:')
 if PRINT_STEP_BOARD: print_board(board_pos)
 # Rule based Sudoku Solver.
 is_valid, stuck, board_pos = remove_invalid(board_pos)
 
 if not is_valid:
 dead_end_counter += 1
 assume_list, possibilities = get_next_assume_candidate(board_pos)
 if PRINT_STEPS: print(f'Dead End Number: {dead_end_counter}!!') 
 if PRINT_STEPS: print_board(board_pos)
 reccursion_depth -= 1
 return False
 # Unable to solve board with the rules of Sudoku, Need to assume a value.
 if stuck:
 if PRINT_STEPS: print('Unable to solve using rules of Sudoku, assuming a value:')
 assume_list, possibilities = get_next_assume_candidate(board_pos)
 org_board = copy.deepcopy(board_pos) # Create Snapshot of board before assuming.
 for assumption in org_board[assume_list[0]][assume_list[1]]:
 board_pos[assume_list[0]][assume_list[1]] = [assumption]
 assumption_counter +=1
 if PRINT_ASSUMPTION: print(f'Assuming {assumption} of {org_board[i_assume][j_assume]} at position ({i_assume}, {j_assume})')
 solve_sudoku(board_pos)
 board_pos = copy.deepcopy(org_board) #Reset board back to Original State. 
 reccursion_depth -= 1
 return False
 print('SOLVED!!!!!')
 solution_counter +=1
 print_board(board_pos)
 if FIRST_SOLUTION_ONLY: sys.exit(0)
 reccursion_depth -= 1
 return True
def main():
 problem1 = [[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]]
 problem2 = [[0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,3,0,8,5],
 [0,0,1,0,2,0,0,0,0],
 [0,0,0,5,0,7,0,0,0],
 [0,0,4,0,0,0,1,0,0],
 [0,9,0,0,0,0,0,0,0],
 [5,0,0,0,0,0,0,7,3],
 [0,0,2,0,1,0,0,0,0],
 [0,0,0,0,4,0,0,0,9]] # Sudoku designed against brute force. Notice Line 1 of solution.
 problem3 = [[1,0,0,0,6,8,0,0,9],
 [0,8,4,9,0,0,0,0,0],
 [0,3,0,0,4,2,0,0,0],
 [0,0,0,5,0,0,0,7,0],
 [7,9,0,0,3,0,4,0,0],
 [0,5,0,0,0,4,9,0,0],
 [0,4,0,0,0,3,0,0,0],
 [0,0,6,0,0,7,0,0,4],
 [0,0,2,0,8,6,0,3,0]]
 problem4 = [[0,0,0,0,3,7,6,0,0],
 [0,0,0,6,0,0,0,9,0],
 [0,0,8,0,0,0,0,0,4],
 [0,9,0,0,0,0,0,0,1],
 [6,0,0,0,0,0,0,0,9],
 [3,0,0,0,0,0,0,4,0],
 [7,0,0,0,0,0,8,0,0],
 [0,1,0,0,0,9,0,0,0],
 [0,0,2,5,4,0,0,0,0]]
 problem5 = [[9,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,1,0,0,7],
 [5,0,0,0,0,3,0,0,4],
 [0,0,7,0,0,0,2,0,0],
 [0,0,3,6,0,8,0,0,0],
 [0,0,0,4,0,0,6,1,0],
 [0,8,5,0,4,0,0,0,0],
 [0,0,0,3,2,0,0,6,0],
 [0,4,0,0,1,0,0,9,0]]
 problem6 = [[3,0,6,0,0,0,0,0,0],
 [0,0,0,0,0,6,0,7,0],
 [0,0,1,0,0,3,0,0,9],
 [2,0,0,7,0,8,0,9,0],
 [0,0,0,0,0,0,5,0,8],
 [0,0,0,1,0,0,2,3,0],
 [0,2,0,5,4,0,0,0,0],
 [0,9,0,0,2,0,0,0,0],
 [0,7,0,0,0,0,8,0,1]] #Use to understand Algorithm, with Print all steps.
 problem7 = [[8,5,0,0,0,2,4,0,0],
 [7,2,0,0,0,0,0,0,9],
 [0,0,4,0,0,0,0,0,0],
 [0,0,0,1,0,7,0,0,2],
 [3,0,5,0,0,0,9,0,0],
 [0,4,0,0,0,0,0,0,0],
 [0,0,0,0,8,0,0,7,0],
 [0,1,7,0,0,0,0,0,0],
 [0,0,0,0,3,6,0,4,0]]
 problem8 = [[0,0,5,3,0,0,0,0,0],
 [8,0,0,0,0,0,0,2,0],
 [0,7,0,0,1,0,5,0,0],
 [4,0,0,0,0,5,3,0,0],
 [0,1,0,0,7,0,0,0,6],
 [0,0,3,2,0,0,0,8,0],
 [0,6,0,5,0,0,0,0,9],
 [0,0,4,0,0,0,0,3,0],
 [0,0,0,0,0,9,7,0,0]]
 problem9 = [[0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0]] # Blank Board.
 problem10= [[8,0,0,0,0,0,0,0,0],
 [0,0,3,6,0,0,0,0,0],
 [0,7,0,0,9,0,2,0,0],
 [0,5,0,0,0,7,0,0,0],
 [0,0,0,0,4,5,7,0,0],
 [0,0,0,1,0,0,0,3,0],
 [0,0,1,0,0,0,0,6,8],
 [0,0,8,5,0,0,0,1,0],
 [0,9,0,0,0,0,4,0,0]]
 problem11= [[8,0,0,6,0,0,9,0,5],
 [0,0,0,0,0,0,0,0,0],
 [0,0,0,0,2,0,3,1,0],
 [0,0,7,3,1,8,0,6,0],
 [2,4,0,0,0,0,0,7,3],
 [0,0,0,0,0,0,0,0,0],
 [0,0,2,7,9,0,1,0,0],
 [5,0,0,0,8,0,0,3,6],
 [0,0,3,0,0,0,0,0,0]] # Multiple Solutions
 
 # Default starting board
 #####################################################
 puzzle = problem11 # Choose problem to solve here.
 #####################################################
 
 board_pos = initiate_board(puzzle)
 print("Trying to Solve Board")
 print_board(puzzle)
 solved = solve_sudoku(board_pos)
if __name__== '__main__':
 main()

OUTPUT

Trying to Solve Board
[8, 0, 0, 6, 0, 0, 9, 0, 5]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 2, 0, 3, 1, 0]
[0, 0, 7, 3, 1, 8, 0, 6, 0]
[2, 4, 0, 0, 0, 0, 0, 7, 3]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 2, 7, 9, 0, 1, 0, 0]
[5, 0, 0, 0, 8, 0, 0, 3, 6]
[0, 0, 3, 0, 0, 0, 0, 0, 0]
SOLVED!!!!!
####### SOLUTION NUMBER 1 #######
[[8], [1], [4], [6], [3], [7], [9], [2], [5]]
[[3], [2], [5], [1], [4], [9], [6], [8], [7]]
[[7], [9], [6], [8], [2], [5], [3], [1], [4]]
[[9], [5], [7], [3], [1], [8], [4], [6], [2]]
[[2], [4], [1], [9], [5], [6], [8], [7], [3]]
[[6], [3], [8], [2], [7], [4], [5], [9], [1]]
[[4], [6], [2], [7], [9], [3], [1], [5], [8]]
[[5], [7], [9], [4], [8], [1], [2], [3], [6]]
[[1], [8], [3], [5], [6], [2], [7], [4], [9]]
Current Board Length: 81
Current Reccursion Depth: 6
Current Number of Dead Ends: 1
Number of assumptions made: 6
SOLVED!!!!!
####### SOLUTION NUMBER 2 #######
[[8], [1], [4], [6], [3], [7], [9], [2], [5]]
[[3], [2], [5], [9], [4], [1], [6], [8], [7]]
[[7], [9], [6], [8], [2], [5], [3], [1], [4]]
[[9], [5], [7], [3], [1], [8], [4], [6], [2]]
[[2], [4], [1], [5], [6], [9], [8], [7], [3]]
[[6], [3], [8], [4], [7], [2], [5], [9], [1]]
[[4], [6], [2], [7], [9], [3], [1], [5], [8]]
[[5], [7], [9], [1], [8], [4], [2], [3], [6]]
[[1], [8], [3], [2], [5], [6], [7], [4], [9]]
Current Board Length: 81
Current Reccursion Depth: 6
Current Number of Dead Ends: 1
Number of assumptions made: 7
SOLVED!!!!!
####### SOLUTION NUMBER 3 #######
[[8], [3], [4], [6], [7], [1], [9], [2], [5]]
[[1], [2], [5], [8], [3], [9], [6], [4], [7]]
[[7], [9], [6], [4], [2], [5], [3], [1], [8]]
[[9], [5], [7], [3], [1], [8], [4], [6], [2]]
[[2], [4], [1], [9], [5], [6], [8], [7], [3]]
[[3], [6], [8], [2], [4], [7], [5], [9], [1]]
[[6], [8], [2], [7], [9], [3], [1], [5], [4]]
[[5], [7], [9], [1], [8], [4], [2], [3], [6]]
[[4], [1], [3], [5], [6], [2], [7], [8], [9]]
Current Board Length: 81
Current Reccursion Depth: 9
Current Number of Dead Ends: 8
Number of assumptions made: 23
SOLVED!!!!!
####### SOLUTION NUMBER 4 #######
[[8], [3], [4], [6], [7], [1], [9], [2], [5]]
[[1], [2], [5], [8], [3], [9], [6], [4], [7]]
[[7], [9], [6], [5], [2], [4], [3], [1], [8]]
[[9], [5], [7], [3], [1], [8], [4], [6], [2]]
[[2], [4], [1], [9], [5], [6], [8], [7], [3]]
[[3], [6], [8], [2], [4], [7], [5], [9], [1]]
[[6], [8], [2], [7], [9], [3], [1], [5], [4]]
[[5], [1], [9], [4], [8], [2], [7], [3], [6]]
[[4], [7], [3], [1], [6], [5], [2], [8], [9]]
Current Board Length: 81
Current Reccursion Depth: 10
Current Number of Dead Ends: 8
Number of assumptions made: 25
SOLVED!!!!!
####### SOLUTION NUMBER 5 #######
[[8], [3], [4], [6], [7], [1], [9], [2], [5]]
[[1], [2], [5], [8], [3], [9], [6], [4], [7]]
[[7], [9], [6], [5], [2], [4], [3], [1], [8]]
[[9], [5], [7], [3], [1], [8], [4], [6], [2]]
[[2], [4], [1], [9], [6], [5], [8], [7], [3]]
[[3], [6], [8], [2], [4], [7], [5], [9], [1]]
[[6], [8], [2], [7], [9], [3], [1], [5], [4]]
[[5], [1], [9], [4], [8], [2], [7], [3], [6]]
[[4], [7], [3], [1], [5], [6], [2], [8], [9]]
Current Board Length: 81
Current Reccursion Depth: 10
Current Number of Dead Ends: 8
Number of assumptions made: 26

• hjpotter92: the output looks weird. if my input was list of list of integers, I'd not expect the result to be yet another wrapping. i.sstatic.net/jxrPC.png
• Uban: Thanks, that is a good observation. I'll fix it.

Answer 1

In addition to the comment, a few more things you can work/focus/improve on:

1. Avoid global variables like corona.

2. Since multiple functions are sharing states, or tracking changes using globals, perhaps use a class? For eg. you can have a Board class, consisting of attributes sectors (\$ 3 \times 3 \$ squares), rows (which iterates over 9 rows) and columns (iterator for columns).

3. [i for i in range(1,10)] is same as list(range(1, 10)).

4. The following DEBUG flags(?):

    PRINT_STEPS = False
    PRINT_STEP_BOARD = False
    PRINT_ASSUMPTION = False
   

   can be removed to make use of python's logging utility. Depending on the depth of logs, you can set severity of log messages.

5. The enumeration doesn't make use of index values i and j anywhere. Remove those:

    def board_length(board_pos):
    total_length = 0
    for row in board_pos:
    for cell in row:
    total_length += len(cell)
    return total_length
   

   which can be further shortened to (untested):

    def board_length(board_pos):
    return sum((sum(map(len, row)) for row in board_pos))
   

6. I tried to enable debuggin, with PRINT_ASSUMPTION set to True, and the following error was raised:

    Traceback (most recent call last):
    File ".code.tio", line 287, in <module>
    main()
    File ".code.tio", line 283, in main
    solved = solve_sudoku(board_pos)
    File ".code.tio", line 159, in solve_sudoku
    if PRINT_ASSUMPTION: print(f'Assuming {assumption} of {org_board[i_assume][j_assume]} at position ({i_assume}, {j_assume})')
    NameError: name 'i_assume' is not defined