sudoku.py

# !/usr/bin/env python
# -*- coding: utf-8 -*-

"""
I know this is a common work, but I was inspired to try implement my
own way after perusing some algorithm and data structures pages I felt
like trying this.
Furthermore it's going to be added to the collection of 2D games that
I am currently working on in pygame.
.
"""

__author__ = "</Dan Rhamba>"
__copyright__ = "Copyright 2019, The Beyond Knowledge Project"
__credits__ = ["The Most High"]
__licence__ = "Dan Rhamba Beyond Knowledge Foundation"
__version__ = "1.0.1"
__maintainer__ = "</Dan Rhamba>"
__email__ = "dnlramba9@gmail.com"
__status__ = "Learning"

import os as _os
import random as _random
import time as _time
from copy import deepcopy as _deepcopy

#import joblib as _joblib


class SudokuError(Exception):
    """Raise exceptions for various sudoku rules where necessary"""
    pass


class Sudoku:
    """Main sudoku class. Employs two backtracking techniques to solve or create sudoku i.e
    a greedy bruteforce approach and an intelligent one. Most methods are static. Just call them without
    instantiating it if all you only need puzzles or solved puzzles. This class is intended to be
    used as a module so it defines additional utilities for that purpose."""

    def __init__(self, grid: list = None):
        """grid is a list containing 9 lists filled with values from 0 - 9 and should
        pass sudoku validity test."""

        if grid is None:
            self.grid = [[0 for i in range(9)] for j in range(9)]
        else:
            if not self.is_9_by_9(grid):
                raise SudokuError('Can only take a 9x9 sudoku puzzle')

            self.grid = _deepcopy(grid)
            if not self.is_valid():
                raise SudokuError('Your passed puzzle is in valid')
            self.grid_copy = _deepcopy(grid)
        self.grid_copy = _deepcopy(self.grid)

    def __str__(self):
        s = ''
        for row in self.grid:
            s += str(row) + '\n'
        return s

    def __eq__(self, other):
        if not isinstance(other, Sudoku):
            raise SudokuError('Cannot compare sudoku object to None sudoku object')
        for i in range(9):
            for j in range(9):
                if self.grid[i][j] != other.grid[i][j]:
                    return False
        return True

    def __hash__(self):
        return hash(str(self.grid))

    @staticmethod
    def is_9_by_9(grid: list) -> bool:
        """checks whether the passed sudoku puzzle/grid is 9x9. If so, it returns
        true otherwise false."""
        if len(grid) != 9:
            return False
        for row in grid:
            if len(row) != 9:
                return False
        return True

    @staticmethod
    def get_indices(index: int) -> list:
        """returns the list of indices that the passed index ranges in a block"""
        if 0 < index > 8:
            raise SudokuError('Invalid column/row number passed.')
        if index < 3:
            return list(range(0, 3))
        elif index < 6:
            return list(range(3, 6))
        else:
            return list(range(6, 9))

    @staticmethod
    def remove_zeros(values: list):
        """removes zeros in passed list."""
        while 0 in values:
            values.remove(0)

    def get_block_values(self, cell: tuple, remove_0: bool = True) -> list:
        """returns members of a block given the cell.
        It will then remove 0 valued cells if remove_0 is true otherwise it will keep them
        Note: Not passing the grid returns the values of the grid initialized with the Sudoku class."""

        self.validate_cell(cell)
        i, j = cell
        r = self.get_indices(i)
        c = self.get_indices(j)
        block_values = []
        for i in r:
            for j in c:
                block_values.append(self.grid[i][j])
        if remove_0:
            self.remove_zeros(block_values)
        return block_values

    def get_row_values(self, i: int, remove_0: bool = True) -> list:
        """returns values of the given row i.
        It will then remove 0 valued cells if remove_0 is true otherwise it will keep them.
        Note: Not passing the grid returns the values of the grid initialized with the Sudoku class."""
        if 0 < i > 8:
            raise SudokuError('Invalid column number passed.')

        row_values = self.grid[i][:]  # Note the copying
        if remove_0:
            self.remove_zeros(row_values)
        return row_values

    def get_column_values(self, j: int, remove_0: bool = True) -> list:
        """return values of column j.
        It will then remove 0 valued cell if remove_0 is true otherwise it will keep them.
        Note: Not passing the grid returns the values of the grid initialized with the Sudoku class."""
        if 0 < j > 8:
            raise SudokuError('Invalid column number passed.')

        column_values = []
        for row in self.grid:
            column_values.append(row[j])
        if remove_0:
            self.remove_zeros(column_values)
        return column_values

    def get_cell_members(self, cell: tuple, remove_0: bool = True) -> list:
        """returns numbers already filled according to sudoku rules.
        It will then remove 0 valued cell if remove_0 is true otherwise it will keep them."""

        self.validate_cell(cell)
        i, j = cell
        block_members = self.get_block_values(cell, remove_0=remove_0)
        row_members = self.get_row_values(i, remove_0=remove_0)
        column_members = self.get_column_values(j, remove_0=remove_0)
        all_members = block_members + row_members + column_members
        if remove_0:
            while 0 in all_members:
                all_members.remove(0)

        return all_members

    @staticmethod
    def validate_cell(cell: tuple, value: int = None):
        """returns true if the passed cell is a valid one, false otherwise.
        cell values should be in range 0-8. If value is passed then it should in range 0-9"""
        i, j = cell
        check = [i, j, value] if value else [i, j]
        for integer in check:
            if 0 > integer > 9:
                raise SudokuError('Invalid value or cell passed')

    def assign(self, cell: tuple, value: int):
        """assigns the value passed to the passed cell. Accepted values range from 0-9"""
        i, j = cell
        self.grid[i][j] = value

    def get_value(self, cell: tuple) -> int:
        """returns value in the passed cell."""
        i, j = cell
        check = [i, j]
        for integer in check:
            if 0 > integer > 8:
                raise SudokuError('Invalid cell passed')
        return self.grid[i][j]

    def accepts(self, cell: tuple, value: int) -> bool:
        """return true if the passed value can be accepted by the passed cell otherwise false."""
        cell_members = self.get_cell_members(cell, remove_0=True)
        return value not in cell_members

    def accepted_values(self, cell: tuple) -> list:
        """returns the compliment of members i.e values that are not yet filled/not members
        of the passed cell."""
        values = set(range(1, 10))
        cell_members = set(self.get_cell_members(cell, remove_0=True))
        return list(values - cell_members)

    def is_occupied(self, cell: tuple) -> bool:
        """returns true if the passed cell is already taken i.e not 0 otherwise false."""
        i, j = cell
        return self.grid[i][j] > 0

    def is_valid(self) -> bool:
        """returns true if our sudoku is valid so far.
        Note: checks even if the grid ain't full i.e solved."""
        for i in range(9):
            for j in range(9):
                cell = i, j
                block_members = self.get_block_values(cell)
                # if they aren't equal then there must be a repeated value
                if len(block_members) != len(set(block_members)):
                    return False
                if i == 0:
                    # only need to check once
                    column_members = self.get_column_values(j)
                    # if they aren't equal then there must be a repeated value
                    if len(column_members) != len(set(column_members)):
                        return False
            row_members = self.get_row_values(i)
            # if they aren't equal then there must be a repeated value
            if len(row_members) != len(set(row_members)):
                return False
        return True

    def is_complete(self) -> bool:
        """checks if our grid is complete returning true, otherwise false."""
        is_valid = self.is_valid()
        if not is_valid:
            raise SudokuError('Cannot check for invalid sudoku')
        for row in self.grid:
            if 0 in row:
                return False
        return True

    def refresh_grid(self):
        self.grid = _deepcopy(self.grid_copy)

    def occupied_cells(self) -> list:
        """return cells that are not zero valued in a list"""
        occupied = []
        for i in range(9):
            for j in range(9):
                if self.is_occupied((i, j)):
                    occupied.append((i, j))
        return occupied

    def empty_cells(self) -> list:
        """return cells that are zero valued in a list"""
        not_occupied_cells = []
        for i in range(9):
            for j in range(9):
                if not self.is_occupied((i, j)):
                    not_occupied_cells.append((i, j))
        return not_occupied_cells

    def empty_cells_count(self) -> int:
        """returns the number of unfilled cells."""
        count = 0
        for row in self.grid:
            count += row.count(0)
        return count

    def minimum_accepted(self) -> tuple:
        """returns the cell with the minimum accepted values and the number of the accepted values in a tuple.
        Simply to see if we can improve efficiency of greedy brute forcing."""
        # get the first empty_cell
        cell = None
        for i in range(9):
            for j in range(9):
                if not self.is_occupied((i, j)):
                    cell = i, j

        if cell is None:
            raise SudokuError('You should not use this method on a solved sudoku puzzle')

        n = len(self.accepted_values(cell))

        for i in range(9):
            for j in range(9):
                if self.is_occupied((i, j)):
                    continue
                m = len(self.accepted_values((i, j)))
                # we do need 0 or any filled cell
                if n > m > 0:
                    n = m
                    cell = i, j
        return cell, n

    def intelligent_algo(self):
        """Tries to apply some reasoning  and tricks to minimise _time complexity
         experienced in greedy brute forcingtechnique"""
        count = 0  # will see how many times we refreshed the grid
        while not self.is_complete():
            cell = self.minimum_accepted()[0]
            values = self.accepted_values(cell)
            try:
                choice = _random.choice(values)
                self.assign(cell, choice)
            except (ValueError, IndexError):
                # cannot be solved so we refresh
                self.refresh_grid()
            count += 1
        return count

    def greedy_brute_force(self):
        """applies back tracking algorithm but with brute_force approach to
         fill the cells with accepted values.
        Note it is an inplace method but return count for analysis purposes as
         with intelligent_algo too."""
        count = 0
        while not self.is_complete():

            for i in range(9):
                for j in range(9):
                    cell = i, j
                    accepted_values = self.accepted_values(cell)
                    if len(accepted_values) == 0 and not self.is_occupied(cell):
                        self.refresh_grid()
                    try:
                        choice = _random.choice(accepted_values)
                        if not self.is_occupied((i, j)):
                            self.assign(cell, choice)
                        else:
                            continue

                    except (IndexError, ValueError):
                        pass

            count += 1

        return count

    def generate_complete_sudoku(self) -> list:
        """returns list of lists of complete sudoku values."""
        sudoku = Sudoku()
        sudoku.intelligent_algo()
        return sudoku.grid

    @staticmethod
    def generate_puzzle(empty_cells: int = 50, from_file=False, filename=None) -> list:
        """generate sudoku puzzle. Unfilled cells will have zeros and will equal
        empty_cells. Tries to first search in file if matching puzzle can be found
        before generating from scratch if from_file is true.
        Note: generating from file creates file in the current working directory, not
        in this module directory even if your match won't be found.."""
        puzzle = _Puzzle(empty_cells=empty_cells)
        if from_file:
            return puzzle.get_from_file(empty_cells=empty_cells, filename=filename).grid
        else:
            return puzzle.create_puzzle(empty_cells=empty_cells)

    @staticmethod
    def solve_puzzle(puzzle: list) -> list:
        """solves the passed puzzle and returns it. raises SudokuError if the
        passed puzzle is invalid"""
        sudoku = Sudoku(grid=puzzle)
        sudoku.intelligent_algo()
        return sudoku.grid

    @staticmethod
    def display(sdk):
        """prints the passed sudoku object or grid. You can pass sudoku object
        or grid in a list of lists."""
        if isinstance(sdk, Sudoku):
            print(sdk)
        elif isinstance(sdk, list):
            for row in sdk:
                print(row)


class _Puzzle:
    """Employs Sudoku class capabilities to generate unique sudoku puzzles.
    Stores the newly generated ones in a dict object as sudoku class. You
    can either choose to generate new ones or use the already generated if
    either fits your needs. The latter is faster."""

    def __init__(self, empty_cells: int = 50):
        """empty cells is the number of cells with zero values to be solved."""
        self.puzzle = self.create_puzzle(empty_cells=empty_cells)

    def __str__(self):
        s = ''
        for row in self.puzzle:
            s += str(row) + '\n'
        return s

    def __eq__(self, other):
        if not isinstance(other, _Puzzle):
            raise SudokuError('Cannot compare puzzle object to None puzzle object')
        for i in range(9):
            for j in range(9):
                if self.puzzle[i][j] != other.puzzle[i][j]:
                    return False
        return True

    def __hash__(self):
        return hash(str(self.puzzle))

    @staticmethod
    def create_puzzle(empty_cells: int = 50) -> list:
        """creates a sudoku puzzle"""
        sudoku = Sudoku()
        sudoku.intelligent_algo()
        count = 1
        while sudoku.empty_cells_count() < empty_cells and count < 100:
            occupied = sudoku.occupied_cells()
            cell = _random.choice(occupied)

            if not sudoku.is_occupied(cell):
                count += 1
                continue
            temp = sudoku.get_value(cell)
            sudoku.assign(cell, 0)

            # back track to check for uniqueness
            # create a copy of grid so far
            copy_grid = _deepcopy(sudoku.grid)
            sudoku_test = Sudoku(grid=copy_grid)
            sudoku_test.intelligent_algo()
            # if n times the solved sudoku is equal then it has to be unique
            for k in range(5):
                sudoku_test2 = Sudoku(grid=copy_grid)
                # if it takes longer to be solved then it has to be unique
                start = _time.time()
                sudoku_test2.intelligent_algo()
                stop = _time.time()
                if stop - start > 20:
                    return sudoku.grid
                if sudoku_test != sudoku_test2:
                    # replace back the last modified cell
                    sudoku.assign(cell, temp)
                    break
            count += 1
        # storing the puzzle before return
        #_Puzzle.store_in_file(sudoku)
        return sudoku.grid

    @staticmethod
    def store_in_file(sudoku: Sudoku, filename: str = None, capacity: int = 10000):
        """stores the passed sudoku in file. To avoid excessive memory usage we set a limit
        of stored sudoku with capacity."""
        if filename is None:
            filename = _os.path.join('res', 'sudoku_puzzles')
        try:
            stored_puzzles = _joblib.load(filename)
            key = len(stored_puzzles) + 1
            stored_puzzles[key] = sudoku
            if len(stored_puzzles) < capacity:
                _joblib.dump(stored_puzzles, filename)
        except FileNotFoundError:
            _joblib.dump({1: sudoku}, filename)

    @staticmethod
    def get_from_file(empty_cells: int = 50, filename: str = None) -> Sudoku:
        """returns Sudoku object from stored from file.
        If empty cells is None, it will return randomly otherwise the one matching the case.
        If no matching case is found or FileNotFoundError is thrown it will generate a new one,
         may take longer in that case."""
        if 17 < empty_cells > 81:
            raise SudokuError('Invalid empty cells. Should be integer between 17 and 81')
        if filename is None:
            filename = _os.path.join('res', 'sudoku_puzzles')
        try:
            stored_puzzles = _joblib.load(filename)
            values = list(stored_puzzles.values())
            _random.shuffle(values)
            for sudoku in values:
                if sudoku.empty_cells_count() == empty_cells:
                    return sudoku
        except FileNotFoundError:
            pass

        grid = _Puzzle.create_puzzle(empty_cells=empty_cells)
        sudoku = Sudoku(grid=grid)
        return sudoku


def main():
    puzzle = Sudoku.generate_puzzle()
    solved_puzzle = Sudoku.solve_puzzle(empty_cells=30)
    print(puzzle)
    print()
    print(solved_puzzle)


if __name__ == '__main__':
    main()