# Working on a Sudoku Solver in Python (Source Code)

This is a document previous to a live code review session.

It has the information to prepare for the upcoming code review session, where I plan to share the lessons learned, decision I took, mistakes I did, refactors I had to overcome, and tentatively we will refactor code in order to add some Unit Testing.

## History

I used to play sudoku with my family, so from time to time I do by myself.

Once I found a sudoku that was impossible and it happened that it was a typo from the newspaper, so, when I found another impossible sudoku I wanted to know if it was me, or if there was a typo or similar, so I decided to write a Sudoku Solver that will solve the sudoku for me.

I had problems solving these two sudokus:

## The Source Code

You can clone the project from here:

https://gitlab.com/carles.mateo/sudo-ku-solver

You will have to install colorama package, as I used it for giving colors to the output:

`pip3 install colorama`

The main program sudokusolver.py:

```import copy
from lib.colorutils import ColorUtils

class SudokuMap():

def __init__(self, i_width, i_height, o_color=ColorUtils()):
self.i_width = i_width
self.i_height = i_height
self.o_color = o_color

self.a_map = self.generate_empty_map()

def generate_empty_map(self):
a_map = []
a_row = []
a_i_possible_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for i_x in range(self.i_width):
a_row.append(a_i_possible_numbers.copy())

for i_y in range(self.i_height):
a_map.append(copy.deepcopy(a_row))

return a_map

def set_number(self, i_number, i_x, i_y):
"""
Sets a well known (already defined in the original map) number for a position
:param i_number:
:param i_x:
:param i_y:
:return:
"""
self.a_map[i_y][i_x] = [i_number]

def detect_and_remove_a_number_from_possibles_from_a_row(self, i_y):
"""
We will elinate this possibility from the row
:return: Boolean
"""

b_found = False
self.o_color.print_label("Detecting numbers to remove from row " + str(i_y))

for i_x in range(0, self.i_width):
a_i_numbers_possible = self.a_map[i_y][i_x]
if len(a_i_numbers_possible) == 1:
b_found = True
i_number_found = self.a_map[i_y][i_x][0]
print("Found a number that will be removed from horizontal and vertical and in quadrant", i_number_found, "at", i_x, i_y)
self.remove_a_number_from_possibles_in_a_row(i_number_to_remove=i_number_found, i_y=i_y)
self.remove_a_number_from_possibles_in_a_column(i_number_to_remove=i_number_found, i_x=i_x)

return b_found

def remove_a_number_from_possibles_in_a_row(self, i_number_to_remove, i_y):
"""
Removes a number from the list of possibles in that row
:param i_number_to_remove:
:param i_y:
:return:
"""

self.o_color.print_label("> Scanning for removing " + str(i_number_to_remove) + " in row " + str(i_y))

for i_x in range(0, self.i_width):
a_i_numbers_possible = self.a_map[i_y][i_x]
if len(a_i_numbers_possible) == 1 and a_i_numbers_possible[0] == i_number_to_remove:
# This is the right cell, ignore it
pass
else:
# Subtract the number from the sequence
if i_number_to_remove in a_i_numbers_possible:
a_i_numbers_possible_old = a_i_numbers_possible.copy()
a_i_numbers_possible.remove(i_number_to_remove)
print("> Removed", i_number_to_remove, "From:", str(i_x) + "x" + str(i_y), a_i_numbers_possible_old, "Pending:", a_i_numbers_possible)
self.a_map[i_y][i_x] = a_i_numbers_possible
if len(a_i_numbers_possible) == 1:
# Trigger it again for the number recently discovered
i_new_number_to_remove = a_i_numbers_possible[0]
self.o_color.print_success("> Found " + str(i_new_number_to_remove) + " From: " + str(i_x) + "x" + str(i_y))
self.remove_a_number_from_possibles_in_a_row(i_number_to_remove=i_new_number_to_remove, i_y=i_y)
self.remove_a_number_from_possibles_in_a_column(i_number_to_remove=i_new_number_to_remove, i_x=i_x)

self.o_color.print_label("> Leaving scan for " + str(i_number_to_remove) + " in row " + str(i_y))

def remove_a_number_from_possibles_in_a_column(self, i_number_to_remove, i_x):
"""
Removes a number from the list of possibles in that row
:param i_number_to_remove:
:param i_y:
:return:
"""

self.o_color.print_label("V Scanning for removing " + str(i_number_to_remove) + " in col " + str(i_x))

for i_y in range(0, self.i_height):
a_i_numbers_possible = self.a_map[i_y][i_x]
if len(a_i_numbers_possible) == 1 and a_i_numbers_possible[0] == i_number_to_remove:
# This is the right cell, ignore it
pass
else:
# Subtract the number from the sequence
if i_number_to_remove in a_i_numbers_possible:
a_i_numbers_possible_old = a_i_numbers_possible.copy()
a_i_numbers_possible.remove(i_number_to_remove)
print("V Removed", i_number_to_remove, "From:", i_x, i_y, a_i_numbers_possible_old, "Pending:", a_i_numbers_possible)
# @TODO: Remove, as it's a pointer it is not needed
self.a_map[i_y][i_x] = a_i_numbers_possible
if len(a_i_numbers_possible) == 1:
# Trigger it again for the number recently discovered
i_new_number_to_remove = a_i_numbers_possible[0]
self.o_color.print_success("Found " + str(i_new_number_to_remove) + " From: " + str(i_x) + " " + str(i_y))
self.remove_a_number_from_possibles_in_a_row(i_number_to_remove=i_new_number_to_remove, i_y=i_y)
self.remove_a_number_from_possibles_in_a_column(i_number_to_remove=i_new_number_to_remove, i_x=i_x)

self.o_color.print_label("V Leaving scan for " + str(i_number_to_remove) + " in col " + str(i_x))

"""

:param i_number_to_remove:
:param i_x:
:param i_y:
:return:
"""

i_x_end = i_x_ini + 2

i_y_end = i_y_ini + 2

for i_y_rel in range(i_y_ini, i_y_end + 1):
for i_x_rel in range(i_x_ini, i_x_end + 1):
a_i_numbers_possible = self.a_map[i_y_rel][i_x_rel]
if len(a_i_numbers_possible) == 1 and a_i_numbers_possible[0] == i_number_to_remove:
# This is the right cell, ignore it
pass
else:
# Subtract the number from the sequence
if i_number_to_remove in a_i_numbers_possible:
a_i_numbers_possible_old = a_i_numbers_possible.copy()
a_i_numbers_possible.remove(i_number_to_remove)
print("X Removed", i_number_to_remove, "From:", i_x_rel, i_y_rel, a_i_numbers_possible_old, "Pending:", a_i_numbers_possible)
# Nota: Here I had a bug and I was "liant-la parda"
# if len(a_i_numbers_possible) == 1:
#     # Trigger it again for the number recently discovered
#     i_new_number_to_remove = a_i_numbers_possible[0]
#     string_ints = [str(int) for int in ints]
#     self.o_color.print_success("X Found " + str(i_new_number_to_remove) + " From: " + str(i_x) + "x" + str(i_y) + "[]")
#     self.remove_a_number_from_possibles_in_a_row(i_number_to_remove=i_new_number_to_remove, i_y=i_y)
#     self.remove_a_number_from_possibles_in_a_column(i_number_to_remove=i_new_number_to_remove, i_x=i_x)

"""

:param i_number_to_remove:
:param i_x:
:param i_y:
:return: b_found
"""

i_x_end = i_x_ini + 2

i_y_end = i_y_ini + 2

i_number_of_occurrences_found = 0
i_x_position_number = 0
i_y_position_number = 0

b_unique = False

for i_y_rel in range(i_y_ini, i_y_end + 1):
for i_x_rel in range(i_x_ini, i_x_end + 1):
a_i_numbers_possible = self.a_map[i_y_rel][i_x_rel]
for i_number_in_possibles in a_i_numbers_possible:
if len(a_i_numbers_possible) > 1 and i_number_in_possibles == i_number_to_check:
# This is the right cell, ignore it
i_number_of_occurrences_found += 1
i_x_position_number = i_x_rel
i_y_position_number = i_y_rel
if i_number_of_occurrences_found > 1:
# Unsuccessful
break

if i_number_of_occurrences_found == 1:
# Success!
a_i_numbers_possible = [i_number_to_check]
self.a_map[i_y_position_number][i_x_position_number] = a_i_numbers_possible
b_unique = True

return b_unique, i_x_position_number, i_y_position_number

def check_if_number_possibles_in_row_is_unique(self, i_number_to_check, i_y):
"""

:param i_number_to_check:
:param i_x:
:param i_y:
:return:
"""

i_number_of_occurrences_found = 0
i_x_position_number = 0
i_y_position_number = 0

b_unique = False

for i_x_rel in range(0, 9):
a_i_numbers_possible = self.a_map[i_y][i_x_rel]
for i_number_in_possibles in a_i_numbers_possible:
if len(a_i_numbers_possible) > 1 and i_number_in_possibles == i_number_to_check:
# This is the right cell, ignore it
i_number_of_occurrences_found += 1
i_x_position_number = i_x_rel
i_y_position_number = i_y
if i_number_of_occurrences_found > 1:
# Unsuccessful
break

if i_number_of_occurrences_found == 1:
# Success!
a_i_numbers_possible = [i_number_to_check]
self.a_map[i_y_position_number][i_x_position_number] = a_i_numbers_possible
b_unique = True

return b_unique, i_x_position_number, i_y_position_number

def get_map_drawing_as_string(self, a_map_alternative=None):
s_map = ""
i_counter_y = 0
s_separator_rows = "="

a_map_to_use = self.a_map
if a_map_alternative is not None:
a_map_to_use = a_map_alternative

s_map = s_map + s_separator_rows * 37 + "\n"
for a_row in a_map_to_use:
i_counter_y += 1
if i_counter_y == 3:
i_counter_y = 0
s_separator_rows = "="
else:
s_separator_rows = "-"

s_map = s_map + "|"
i_counter = 0
for a_i_numbers_possible in a_row:
i_counter += 1

if len(a_i_numbers_possible) == 1:
s_number = str(a_i_numbers_possible[0])
else:
s_number = " "

if i_counter == 3:
s_separator = "|"
i_counter = 0
else:
s_separator = "¦"
s_map = s_map + " " + s_number + " " + s_separator
s_map = s_map + "\n"

s_map = s_map + s_separator_rows * 37 + "\n"

# Replace 0 by " "
s_map = s_map.replace("0", " ")

s_map = s_map + "\n\n"
i_total_numbers_found, a_s_numbers_found = self.get_total_numbers_found()
s_map = s_map + "Total numbers found: " + str(i_total_numbers_found) + " Numbers found: " + " ".join(a_s_numbers_found) + "\n"

return s_map

def get_map_drawing_of_possibles_as_string(self, a_map_alternative=None):
s_map = ""
i_counter_y = 0
s_separator_rows = "="

a_map_to_use = self.a_map
if a_map_alternative is not None:
a_map_to_use = a_map_alternative

s_map = s_map + self.o_color.color_blue(s_separator_rows * ((9 * ( 9 + 2 )) + 10)) + "\n"
for a_row in a_map_to_use:
i_counter_y += 1
if i_counter_y == 3:
i_counter_y = 0
s_separator_rows = "="
else:
s_separator_rows = "-"

s_map = s_map + self.o_color.color_blue("|")
i_counter = 0
for a_i_numbers_possible in a_row:
i_counter += 1

if len(a_i_numbers_possible) == 1:
# The right number
s_number = str(a_i_numbers_possible[0]).center(9)
s_number = self.o_color.color_success(s_number)
else:
a_i_numbers_possible_string = []
for i_number in a_i_numbers_possible:
s_number = str(i_number)
# Replace by the color sequence
if i_number == 2:
s_number = self.o_color.color_red(s_number)
if i_number == 3:
s_number = self.o_color.color_yellow(s_number)
if i_number == 4:
self.o_color.color_magenta(s_number)
a_i_numbers_possible_string.append(s_number)
# s_number = "".join(a_i_numbers_possible_string).ljust(9)
s_number = "".join(a_i_numbers_possible_string) + " " * (9-len(a_i_numbers_possible))

if i_counter == 3:
s_separator = self.o_color.color_blue("|")
i_counter = 0
else:
s_separator = self.o_color.color_blue("¦")
s_map = s_map + " " + s_number + " " + s_separator
s_map = s_map + "\n"

s_map = s_map + self.o_color.color_blue(s_separator_rows * ((9 * (9 + 2)) + 10)) + "\n"

# Replace 0 by " "
s_map = s_map.replace("0", " ")

return s_map

def get_total_numbers_found(self):

i_total_numbers_found = 0
a_s_numbers_found = []

for i_y in range(0, self.i_height):
for i_x in range(0, self.i_width):
a_i_numbers_possible = self.a_map[i_y][i_x]
if len(a_i_numbers_possible) == 1:
i_total_numbers_found = i_total_numbers_found + 1
i_number_found = self.a_map[i_y][i_x][0]
s_number_found = str(i_number_found)
if s_number_found not in a_s_numbers_found:
a_s_numbers_found.append(s_number_found)

return i_total_numbers_found, a_s_numbers_found

if __name__ == "__main__":

o_color = ColorUtils()

o_map = SudokuMap(9, 9, o_color=o_color)
o_map.set_number(i_number=1, i_x=1, i_y=0)
o_map.set_number(3, 4, 0)
o_map.set_number(8, 7, 0)

o_map.set_number(8, 0, 1)
o_map.set_number(7, 3, 1)
o_map.set_number(4, 5, 1)
o_map.set_number(6, 8, 1)

o_map.set_number(3, 2, 2)
o_map.set_number(9, 6, 2)

o_map.set_number(2, 1, 3)
o_map.set_number(4, 4, 3)
o_map.set_number(6, 7, 3)

o_map.set_number(5, 0, 4)
o_map.set_number(6, 3, 4)
o_map.set_number(2, 5, 4)
o_map.set_number(8, 8, 4)

o_map.set_number(3, 1, 5)
o_map.set_number(8, 4, 5)
o_map.set_number(7, 7, 5)

o_map.set_number(2, 2, 6)
o_map.set_number(6, 6, 6)

o_map.set_number(9, 0, 7)
o_map.set_number(4, 3, 7)
o_map.set_number(3, 5, 7)
o_map.set_number(2, 8, 7)

o_map.set_number(8, 1, 8)
o_map.set_number(6, 4, 8)
o_map.set_number(1, 7, 8)

# Extra
# o_map.set_number(2, 0, 0)

# Speculative
o_map.set_number(7, 0, 3)

# Another map
o_map2 = SudokuMap(9, 9, o_color=o_color)
o_map2.set_number(i_number=5, i_x=0, i_y=0)
o_map2.set_number(i_number=9, i_x=5, i_y=0)

o_map2.set_number(i_number=7, i_x=2, i_y=1)
o_map2.set_number(i_number=2, i_x=7, i_y=1)

o_map2.set_number(i_number=2, i_x=0, i_y=2)
o_map2.set_number(i_number=3, i_x=4, i_y=2)
o_map2.set_number(i_number=1, i_x=5, i_y=2)
o_map2.set_number(i_number=9, i_x=7, i_y=2)

o_map2.set_number(i_number=7, i_x=0, i_y=3)
o_map2.set_number(i_number=1, i_x=2, i_y=3)
o_map2.set_number(i_number=6, i_x=3, i_y=3)
o_map2.set_number(i_number=9, i_x=4, i_y=3)
o_map2.set_number(i_number=4, i_x=8, i_y=3)

o_map2.set_number(i_number=1, i_x=4, i_y=4)

o_map2.set_number(i_number=6, i_x=0, i_y=5)
o_map2.set_number(i_number=7, i_x=4, i_y=5)
o_map2.set_number(i_number=4, i_x=5, i_y=5)
o_map2.set_number(i_number=3, i_x=6, i_y=5)
o_map2.set_number(i_number=1, i_x=8, i_y=5)

o_map2.set_number(i_number=5, i_x=1, i_y=6)
o_map2.set_number(i_number=3, i_x=3, i_y=6)
o_map2.set_number(i_number=6, i_x=4, i_y=6)
o_map2.set_number(i_number=8, i_x=8, i_y=6)

o_map2.set_number(i_number=6, i_x=1, i_y=7)
o_map2.set_number(i_number=7, i_x=6, i_y=7)

o_map2.set_number(i_number=9, i_x=3, i_y=8)
o_map2.set_number(i_number=3, i_x=8, i_y=8)

# Extra help while not implemented the best algorithm
# =============================================================================================================
# |     5     ¦ 148       ¦ 48        |     7     ¦     2     ¦     9     | 148       ¦     3     ¦     6     |
# -------------------------------------------------------------------------------------------------------------
# | 13489     ¦ 13489     ¦     7     | 48        ¦ 48        ¦     6     | 148       ¦     2     ¦     5     |
# -------------------------------------------------------------------------------------------------------------
# |     2     ¦ 48        ¦     6     |     5     ¦     3     ¦     1     | 48        ¦     9     ¦     7     |
# =============================================================================================================
# |     7     ¦ 38        ¦     1     |     6     ¦     9     ¦ 358       |     2     ¦ 58        ¦     4     |
# -------------------------------------------------------------------------------------------------------------
# | 348       ¦ 2348      ¦ 3458      | 28        ¦     1     ¦ 358       |     6     ¦     7     ¦     9     |
# -------------------------------------------------------------------------------------------------------------
# |     6     ¦ 289       ¦ 589       | 28        ¦     7     ¦     4     |     3     ¦ 58        ¦     1     |
# =============================================================================================================
# | 14        ¦     5     ¦     2     |     3     ¦     6     ¦     7     |     9     ¦ 14        ¦     8     |
# -------------------------------------------------------------------------------------------------------------
# | 3489      ¦     6     ¦ 3489      |     1     ¦ 458       ¦ 58        |     7     ¦ 45        ¦     2     |
# -------------------------------------------------------------------------------------------------------------
# | 148       ¦     7     ¦ 48        |     9     ¦ 458       ¦     2     | 145       ¦     6     ¦     3     |
# =============================================================================================================
# By best algorithm I mean that the last in the middle vertical quadrant from the top right horizontally,
# only 5 can be in a column. That clarifies that 5 must go to the other column in last quadrant, first column. Coord 6x8
# o_map2.set_number(i_number=5, i_x=6, i_y=8)
# ERROR traces from a bug fixed to mentioned during the code review
# Surprisingly this fails
# > Leaving scan for 8 in row1
# V Scanning for removing 8 in col 4
# V Removed 8 From: 4 7 [5, 8] Pending: [5]
# Found 5 From: 4 7
#
# > Scanning for removing 5 in row 7
# > Removed 5 From: 5 7 [5, 8] Pending: [8]
# > Found 8 From: 5 7
#
# > Scanning for removing 8 in row 7
# > Removed 8 From: 0 7 [3, 8] Pending: [3]
# > Found 3 From: 0 7

o_map = o_map2

print(o_map.get_map_drawing_as_string())

b_changes_found = True
while b_changes_found is True:
b_changes_found = False

for i_y in range(0, o_map.i_height):
b_found = o_map.detect_and_remove_a_number_from_possibles_from_a_row(i_y=i_y)
if b_found is True:
print(o_map.get_map_drawing_as_string())

for i_y in range(0, o_map.i_height):
o_map.o_color.print_label("Scanning quadrants for row " + str(i_y))
for i_number in range(1, 10):
for i_x in range(0, o_map.i_width):
b_found, i_x_found, i_y_found = o_map.check_if_number_possibles_in_quadrant_is_unique(i_number_to_check=i_number, i_x=i_x, i_y=i_y)
if b_found is True:
# Search again
b_changes_found = True
o_map.remove_a_number_from_possibles_in_a_row(i_number_to_remove=i_number, i_y=i_y_found)
o_map.remove_a_number_from_possibles_in_a_column(i_number_to_remove=i_number, i_x=i_x_found)

b_found, i_x_found, i_y_found = o_map.check_if_number_possibles_in_row_is_unique(i_number_to_check=i_number, i_y=i_y)
if b_found is True:
b_changes_found = True
o_map.remove_a_number_from_possibles_in_a_column(i_number_to_remove=i_number, i_x=i_x_found)

if b_changes_found is True:
print(o_map.get_map_drawing_as_string())

# @TODO: Implement check if number in quadrant can only go to a column, to remove the non possible in that column from another quadrant
# @TODO: Implement check if in a line only one number can go to a column.

print(o_map.get_map_drawing_as_string())
print(o_map.get_map_drawing_of_possibles_as_string())
```

The color library lib/colorutils.py:

```from colorama import Fore, Back, Style , init

class ColorUtils:

def __init__(self):
# For Colorama on Windows
init()

def print_error(self, m_text, s_end="\n"):
"""
Prints errors in Red.
:param s_text:
:return:
"""

# If they pass numbers
s_text = str(m_text)

print(Fore.RED + s_text)
print(Style.RESET_ALL, end=s_end)

def print_success(self, m_text, s_end="\n"):
"""
Prints errors in Green.
:param s_text:
:return:
"""

# If they pass numbers
s_text = str(m_text)
print(Fore.GREEN + s_text)
print(Style.RESET_ALL, end=s_end)

def color_success(self, m_text):
"""
Colors only this
:param m_text:
:return:
"""

s_text = str(m_text)
return Fore.GREEN + s_text + Fore.RESET

def color_black(self, m_text):
s_text = str(m_text)
return Fore.BLACK + s_text + Fore.RESET

def color_blue(self, m_text):
s_text = str(m_text)
return Fore.BLUE + s_text + Fore.RESET

def color_red(self, m_text):
s_text = str(m_text)
return Fore.RED + s_text + Fore.RESET

def color_yellow(self, m_text):
s_text = str(m_text)
return Fore.YELLOW + s_text + Fore.RESET

def color_magenta(self, m_text):
s_text = str(m_text)
return Fore.MAGENTA + s_text + Fore.RESET

def print_label(self, m_text, s_end="\n"):
"""
Prints a label and not the end line
:param s_text:
:return:
"""

# If they pass numbers
s_text = str(m_text)

print(Fore.BLUE + s_text, end="")
print(Style.RESET_ALL, end=s_end)

def return_text_blue(self, s_text):
"""
Restuns a Text
:param s_text:
:return: String
"""
s_text_return = Fore.BLUE + s_text + Style.RESET_ALL
return s_text_return
```

# A live session refactoring and adding Unit Testing to my Python3 project cmemgzip

I refactor and add unit testing to my actual project cmemgzip while I comment every step so you can learn the whys and the reasoning.

Open video in full screen with max 1080 quality, in order to see the code clearly.

Update 2021-03-03: I added a third part. I’m tired but still is worth watching.