# !/usr/bin/env python # -*- coding: utf-8 -*- """ I know this is a common work, but I was inspired to try to implement my own way of solving 9 by 9 sudoku puzzles after reading some algorithm and data strucures books. Furthermore it's going to be added to the collection of 2D games that I am currently working on in pygame. Due to sololearn time limit, I have limited the empty_cells_count to 30 but you can increase it if you wish so in your machine. """ __author__ = "" __copyright__ = "Copyright 2019, The Beyond Knowledge Project" __credits__ = ["The Most High"] __licence__ = "can't tell" __version__ = "1.0.1" __maintainer__ = "" __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 print(__doc__) class SudokuError(Exception): """Raises 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 need is 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: """generates 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(3): 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(empty_cells=30) solved_puzzle = Sudoku.solve_puzzle(puzzle) print('\nSudoku puzzle\n') Sudoku.display(puzzle) print('\n\nsolved puzzle\n') Sudoku.display(solved_puzzle) if __name__ == '__main__': main()

my_sudoku_logic