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