# Sudoku Solver using rules of Sudoku and backtracking

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
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)

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}")

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 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:
assume_list, possibilities = get_next_assume_candidate(board_pos)
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
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
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
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
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

• 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 Commented Sep 16, 2020 at 5:53
• Thanks, that is a good observation. I'll fix it.
– Uban
Commented Sep 16, 2020 at 12:57

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)


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