Working on a Sudoku Solver in Python (Source Code)
First Published: .
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.
The bad guys
I had problems solving these two sudokus:
Some Screenshots
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)
self.remove_a_number_from_possibles_in_quadrant(i_number_to_remove=i_number_found, i_x=i_x, i_y=i_y)
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.remove_a_number_from_possibles_in_quadrant(i_number_to_remove=i_new_number_to_remove, i_x=i_x, i_y=i_y)
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.remove_a_number_from_possibles_in_quadrant(i_number_to_remove=i_new_number_to_remove, i_x=i_x, i_y=i_y)
self.o_color.print_label("V Leaving scan for " + str(i_number_to_remove) + " in col " + str(i_x))
def remove_a_number_from_possibles_in_quadrant(self, i_number_to_remove, i_x, i_y):
"""
:param i_number_to_remove:
:param i_x:
:param i_y:
:return:
"""
i_x_quadrant = int(i_x / 3)
i_y_quadrant = int(i_y / 3)
i_x_ini = i_x_quadrant * 3
i_x_end = i_x_ini + 2
i_y_ini = i_y_quadrant * 3
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)
def check_if_number_possibles_in_quadrant_is_unique(self, i_number_to_check, i_x, i_y):
"""
:param i_number_to_remove:
:param i_x:
:param i_y:
:return: b_found
"""
i_x_quadrant = int(i_x / 3)
i_y_quadrant = int(i_y / 3)
i_x_ini = i_x_quadrant * 3
i_x_end = i_x_ini + 2
i_y_ini = i_y_quadrant * 3
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
Rules for writing a Comment