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