A simple Sudoku Solver in Python

sudoku.py

# Created by jerry Shikanga
# Date :  01/07/2020
# Simple program to fill Sudoku
# TODO: Reduce number of loops
# Allow visual input
# Fix row/column setting/retrieval

from unittest import TestCase


class Box:
    """
    This will hold an individual element in the sudoku grid
    """
    filled = False
    value = None
    grid9by9x = 0  # X coordinate on the ancestor grid
    grid9by9y = 0  # Y coordinate on the ancestor grid
    parent_grid = None

    possibilities = []  # All the possible values that can be used on the field. When only one is remaining then sdet
    # that as the value 

    def __init__(self, x, y, parent_grid, value=0):
        self.grid9by9x = x
        self.grid9by9y = y
        self.value = value
        if value != 0:
            self.filled = True
        self.parent_grid = parent_grid
        if not self.value or self.filled:
            self.possibilities = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self)

    def has_only_one_possible_value(self):
        return len(self.possibilities) == 1

    def get_sub_grid(self):
        x = int((self.grid9by9x/3))
        y = int((self.grid9by9y/3))
        return self.parent_grid.sub_grids[x][y]

    # TODO : The below two functions return flipped results. To work on them
    def get_column(self):
        return self.parent_grid.columns[self.grid9by9y]

    def get_row(self):
        return self.parent_grid.rows[self.grid9by9x]

    def try_fill_possible_values(self):
        """
        Algo : firs check he grid, then the row then the column.
        If any has a possible va;ue we remove it from the list.
        If only one item remains then that's the answer
        :return:
        """
        if not self.filled:
            l_sub_grid = [v.value for v in self.get_sub_grid().get_boxes()]
            for v in l_sub_grid:
                if v in self.possibilities:
                    self.possibilities.remove(v)

            l_row = [v.value for v in self.get_row().get_boxes()]
            for v in l_row:
                if v in self.possibilities:
                    self.possibilities.remove(v)

            l_column = [v.value for v in self.get_column().get_boxes()]
            for v in l_column:
                if v in self.possibilities:
                    self.possibilities.remove(v)
            if self.has_only_one_possible_value():
                self.value = self.possibilities[0]
                self.filled = True


class Grid3By3:
    x_start = 0
    x_end = 0
    y_start = 0
    y_end = 0
    parent_grid = None

    def __init__(self, x_start, x_end, y_start, y_end, parent_grid):
        self.x_start = x_start
        self.x_end = x_end
        self.y_start = y_start
        self.y_end = y_end
        self.parent_grid = parent_grid

    def __str__(self):
        return f'XS: {self.x_start} XE: {self.x_end} YS: {self.y_start} YE: {self.y_end}'

    def __repr__(self):
        return str(self)

    def get_boxes(self):
        boxes = []
        for x in range(self.x_start, self.x_end+1):
            for y in range(self.y_start, self.y_end+1):
                boxes.append(self.parent_grid.boxes[x][y])
        return boxes

    def visualize(self):
        str_out = ""
        for y in range(self.y_start, self.y_end + 1):
            for x in range(self.x_start, self.x_end+1):
                str_out += f" {self.parent_grid.boxes[x][y]}"
                if (x+1) % 3 == 0:
                    str_out += "\n"
        return str_out


class Row1by9:
    x = 0
    parent_grid = None

    def __init__(self, x, parent_grid):
        self.x = x
        self.parent_grid = parent_grid

    def __repr__(self):
        return str(self)

    def __str__(self):
        return f'X : {self.x}'

    def get_boxes(self):
        boxes = []
        for y in range(9):
            boxes.append(self.parent_grid.boxes[self.x][y])
        return boxes

    def visualize(self):
        str_out = ""
        for i, box in enumerate(self.get_boxes()):
            str_out += f"{box.value}  "
            if i in [2, 5]:
                str_out += '| '
        return str_out


class Column1by9:
    y = 0
    parent_grid = None

    def __init__(self, y, parent_grid):
        self.y = y
        self.parent_grid = parent_grid

    def __str__(self):
        return f"Y : {self.y}"

    def __repr__(self):
        return str(self)

    def get_boxes(self):
        boxes = []
        for x in range(9):
            boxes.append(self.parent_grid.boxes[x][self.y])
        return boxes

    def visualize(self):
        str_out = ""
        for i, box in enumerate(self.get_boxes()):
            str_out += f" {box.value}\n"
            if i in [2, 5]:
                str_out += "---\n"
        return str_out


class Grid9by9:
    boxes = []
    rows = []
    columns = []
    sub_grids = []

    def __init__(self, initial_grid=None):
        self.init_boxes(initial_grid=initial_grid)
        self.init_rows()
        self.init_columns()
        self.init_sub_grids()

    def __str__(self):
        return self.visualize()

    def __repr__(self):
        return str(self)

    def init_boxes(self, initial_grid=None):
        self.boxes = [[] for i in range(9)]
        for x in range(9):
            self.boxes[x] = [[] for i in range(9)]
            for y in range(9):
                if initial_grid:
                    box = Box(x, y, self, initial_grid[x][y])
                else:
                    box = Box(x, y, self)
                self.boxes[x][y] = box
        return self.boxes

    def init_rows(self):
        self.rows = [Row1by9(y, self) for y in range(9)]

    def init_columns(self):
        self.columns = [Column1by9(x, self) for x in range(9)]

    def visualize_subgrids(self):
        s_out = ""
        for y in range(3):
            for x in range(3):
                s_out += f'{self.sub_grids[x][y]}         '
                if x == 2: s_out += '\n'
        return s_out

    def init_sub_grids(self):
        self.sub_grids = [None for _ in range(3)]
        for i in range(3):
            self.sub_grids[i] = [None for _ in range(3)]
        x_index, y_index = 0, 0

        for y in (range(0, 9, 3)):
            y_start, y_end = y, y + 2
            for x in range(0, 9, 3):
                x_start, x_end = x, x + 2
                grid = Grid3By3(x_start, x_end, y_start, y_end, self)
                self.sub_grids[x_index][y_index] = grid
                x_index += 1
            x_index, y_index = 0, y_index + 1

    def visualize(self):
        str_out = "--------- --------- ---------\n"
        for y in range(len(self.boxes[0])):
            for x in range(len(self.boxes)):
                str_out += f"{self.boxes[x][y]}  "
                # str_out += f"{self.boxes[x][y]}  |"
                if x in [2, 5]:
                    str_out += "| "
                if x == 8:
                    str_out += "\n"
            if y in [2, 5, 8]:
                str_out += "--------- --------- ---------\n"
        return str_out

    def get_unfilled_count(self):
        count = 0
        for y in range(9):
            for x in range(9):
                if self.boxes[x][y].value == 0:
                    count += 1
        return count

    def run_single_fill_check(self):
        for y in range(9):
            for x in range(9):
                self.boxes[x][y].try_fill_possible_values()

    @property
    def is_fully_filled(self):
        return self.get_unfilled_count() == 0

    def run_check_iterative(self):
        epochs = 0

        while not self.is_fully_filled:
            self.run_single_fill_check()
            unfilled = self.get_unfilled_count()
            print(f"Epoch {epochs} : Unfilled : {unfilled}")
            epochs += 1

# from kahuna.apps.sudoku import Grid9by9; g = Grid9by9(); print(g.visualize())
# from kahuna.apps.sudoku import initial_grid, Grid9by9; g = Grid9by9(initial_grid); print(g.visualize())


class SudokuTest(TestCase):
    def test_initialization(self):
        self.sample_grid = [
            [9, 0, 2,    8, 1, 0,   0, 0,  5],
            [8, 1, 5,    3, 0, 4,   0, 2,  6],
            [0, 3, 0,    0, 0, 0,   8, 0,  0],


            [5, 8, 0,    0, 7, 0,   0, 0,  3],
            [0, 2, 4,    9, 0, 1,   6, 0,  0],
            [0, 0, 0,    0, 3, 0,   2, 5,  4],


            [6, 0, 8,    0, 0, 3,   4, 0,  0],
            [0, 4, 0,    0, 8, 0,   1, 0,  0],
            [0, 0, 1,    0, 0, 6,   5, 0,  8],
        ]
        self.grid9by9 = Grid9by9(self.sample_grid)
        for x in range(len(self.sample_grid)):
            for y in range(len(self.sample_grid[x])):
                self.assertEqual(self.grid9by9.boxes[x][y].value, self.sample_grid[x][y])