1. Josh VanderLinden
  2. sudoku

Commits

Josh VanderLinden  committed e957816

Added a README, JigsawSudoku, screenshots

I wrote a simple JigsawSudoku class, which inherits from Sudoku and specifies alternative regions. The output is also colored with JigsawSudoku, instead of printing dividing lines using ASCII.

  • Participants
  • Parent commits 063974d
  • Branches default

Comments (0)

Files changed (10)

File MANIFEST.in

View file
  • Ignore whitespace
-include LICENSE
+include LICENSE README
 recursive-include sudokulib *.py
+recursive-include doc *.*
 

File README

View file
  • Ignore whitespace
+sudokulib is a collection of tools that are useful for generating solutions to 
+Sudoku puzzles.  It uses a recursive backtracking algorithm (originally 
+written by Jeremy Brown, Cel Destept), and is capable of generating a 3x3 
+Sudoku in ~0.015 seconds.  It can also generate 4x4 Sudokus in ~0.100 seconds 
+(sometimes longer).
+
+Some 5x5 grids have been generated in a matter of seconds using this library, 
+but I've also seen the program run for hours without successfully generating 
+a 5x5.  Anything beyond 5x5 always seems to take a long time.
+
+You can solve Sudoku puzzles using this library by calling the ``init_grid`` 
+method of an instance of ``Sudoku``.  This method takes two types of values. 
+Where ``n`` is the grid size:
+
+* a 1-dimensional list with n^4 values
+* a multi-dimensional list with n^2 lists with n^2 values each.  Each list 
+  represents a row in the grid
+
+The values in the list(s) provided to ``init_grid`` must be numeric and 
+greater than 0 but less than n^2 in order to appear in the starting grid. Any 
+other values will be ignored, and the puzzle will be solved with no 
+consideration for such values.
+
+The library also provides utilities for generating starting grids, so you can 
+play Sudoku instead of just generating solutions.  There are several difficulty 
+levels to choose from.
+
+Also included in the distribution is a sample class for generating "jigsaw" 
+variations of Sudoku.  This class will occasionally generate solvable grids 
+within a second or two, but it takes much longer more often than not.
+

File doc/README

View file
  • Ignore whitespace
+../README

File doc/jigsaw.png

  • Ignore whitespace
Added
New image

File doc/jigsaw2.png

  • Ignore whitespace
Added
New image

File setup.py

View file
  • Ignore whitespace
 from distutils.core import setup
 from sudokulib import __version__
+import os
 
 setup(
     name='sudokulib',
     version=__version__,
     description='Tools for generating solutions and starting grids for Sudoku.',
-    long_description="""sudokulib is a collection of tools that are useful for 
-generating solutions to Sudoku puzzles.  It uses a recursive backtracking 
-algorithm (originally written by Jeremy Brown, Cel De\xc5\x9ftept), and is 
-capable of generating a 3x3 Sudoku in ~0.015 seconds.  It can also generate 
-4x4 Sudokus in ~0.100 seconds (sometimes longer).
-
-Some 5x5 grids have been generated in a matter of seconds using this library, 
-but I've also seen the program run for hours without successfully generating 
-a 5x5.  Anything beyond 5x5 always seems to take a long time.
-
-The library also provides utilities for generating starting grids, so you can 
-play Sudoku instead of just generating solutions.  There are several difficulty 
-levels to choose from.""",
+    long_description=open('README', 'r').read(),
     keywords='sudoku',
     author='Josh VanderLinden',
     author_email='codekoala at gmail com',
     package_dir={'sudokulib': 'sudokulib'},
     packages=['sudokulib'],
     platforms=['Windows', 'Linux', 'OSX'],
+    classifiers=[
+        "Development Status :: 5 - Production/Stable",
+        "Environment :: Console",
+        "Intended Audience :: Developers",
+        "License :: OSI Approved :: BSD License",
+        "Natural Language :: English",
+        "Operating System :: OS Independent",
+        "Programming Language :: Python",
+        "Programming Language :: Python :: 2.6",
+        "Topic :: Games/Entertainment :: Puzzle Games",
+        "Topic :: Software Development :: Libraries :: Python Modules",
+        "Topic :: Utilities",
+    ],
 )
 

File sudokulib/__init__.py

View file
  • Ignore whitespace
-__version__ = '0.5a'
+__version__ = '0.6a'
 

File sudokulib/decorators.py

View file
  • Ignore whitespace
         return func(self, num)
     return wrapped
 
+def requires_solution(func):
+    """Solves the puzzle before returning"""
+
+    def wrapped(self, *args, **kwargs):
+        if None in self.solution:
+            self.solve()
+
+        return func(self, *args, **kwargs)
+    return wrapped
+

File sudokulib/jigsaw.py

View file
  • Ignore whitespace
+import sys
+
+from decorators import requires_solution
+from sudoku import Sudoku
+
+class JigsawSudoku(Sudoku):
+    VALID_SIZES = (3,)
+    REGIONS = (
+        ( 0, 1, 2, 9,10,11,18,27,28),
+        ( 3,12,13,14,23,24,25,34,35),
+        ( 4, 5, 6, 7, 8,15,16,17,26),
+        (19,20,21,22,29,36,37,38,39),
+        (30,31,32,33,40,47,48,49,50),
+        (41,42,43,44,51,58,59,60,61),
+        (45,46,55,56,57,66,67,68,77),
+        (52,53,62,69,70,71,78,79,80),
+        (54,63,64,65,72,73,74,75,76),
+    )
+    REGION_COLORS = (
+        (41, 30), (42, 30), (43, 30),
+        (44, 30), (45, 30), (46, 30),
+        (47, 30), (41, 30), (42, 30),
+    )
+
+    def get_region(self, row, col):
+        index = self.row_col_to_index(row, col)
+        return self.get_region_by_index(index)
+
+    def get_region_by_index(self, index):
+        """Returns values used in the region at the specified index"""
+
+        for region in JigsawSudoku.REGIONS:
+            if index in region:
+                return [self.solution[i] for i in region]
+
+        raise ValueError('Invalid index')
+
+    @requires_solution
+    def print_grid(self, grid):
+        """Prints a nicely formatted version of the Sudoku grid"""
+
+        fmt = '\033[%s;%sm'
+        norm = '\033[0m'
+        field_width = len(str(self.side_length)) + 2
+
+        for i, val in enumerate(grid):
+            if i % 9 == 0 and i > 0:
+                sys.stdout.write('\n')
+
+            for rid, r in enumerate(self.REGIONS):
+                if i in r:
+                    region_id = rid
+                    break
+
+            col = fmt % self.REGION_COLORS[region_id]
+            val = str(val).center(field_width)
+            sys.stdout.write('%s%s%s' % (col, val, norm))
+
+        sys.stdout.write('\n')
+
+def main():
+    s = JigsawSudoku()
+    #s.print_masked()
+    #print '=' * 50
+    #s.print_solution()
+
+    s.clear()
+    s.init_grid([3,0,0,0,0,0,0,0,4,0,0,2,0,6,0,1,0,0,0,1,0,9,0,8,0,2,0,0,0,5,0,0,0,6,0,0,0,2,0,0,0,0,0,1,0,0,0,9,0,0,0,8,0,0,0,8,0,3,0,4,0,6,0,0,0,4,0,1,0,9,0,0,5,0,0,0,0,0,0,0,7])
+    s.print_masked()
+    print '=' * 50
+    s.print_solution()
+
+if __name__ == '__main__':
+    main()

File sudokulib/sudoku.py

View file
  • Ignore whitespace
 import random
 import time
 
-from decorators import handle_negative, check_length
+from decorators import handle_negative, check_length, requires_solution
 
 MIN = -1
 EASY = 0
 GOOD_LUCK = 5
 
 class Sudoku(object):
+    VALID_SIZES = (2, 3, 4, 5)
     SCALE =  {
         MIN: 0.50,
         EASY: 0.40,
 
         self.clear()
 
+    def init_grid(self, values):
+        """Initializes the grid with some existing values."""
+
+        validate = lambda v: (str(v).isdigit() and v > 0 and v <= self.side_length) and v or None
+        if len(values) == self.square:
+            # 1-dimensional list of values
+            self.solution = [validate(v) for v in values]
+        elif len(values) == self.side_length:
+            # multi-dimensional list of values: [[row 1], [row 2], ..., [row n]]
+            for i, row in enumerate(values):
+                self.set_row(i, [validate(v) for v in row])
+
     def clear(self):
         """Cleans up the Sudoku solution"""
 
         self.solution = [None for i in range(self.square)]
 
-    def __row_col_to_index(self, row, col):
+    def row_col_to_index(self, row, col):
         """Translates a (row, col) into an index in our 1-dimensional list"""
 
         return (row * self.side_length) + col
 
-    def __index_to_row_col(self, index):
+    def index_to_row_col(self, index):
         """Translates an index in our 1-dimensional list to a (row, col)"""
 
         return divmod(index, self.side_length)
 
     def set_grid_size(self, grid_size):
-        self.grid_size = grid_size
+        """Sets the grid size"""
+
+        if grid_size in self.VALID_SIZES:
+            self.grid_size = grid_size
+        else:
+            raise ValueError('Invalid size.  Options are: %s' % (self.VALID_SIZES, ))
 
     def set_difficulty(self, difficulty):
-        self.difficulty = difficulty
+        """Sets the difficulty level for a masked grid"""
+
+        valid_diff = self.SCALE.keys()
+        valid_diff.remove(MIN)
+
+        if difficulty in valid_diff:
+            self.difficulty = difficulty
+        else:
+            raise ValueError('Invalid difficulty level.  Options are: %s' % (valid_diff,))
 
     @property
+    @requires_solution
     def masked_grid(self):
         """Generates and caches a Sudoku with several squares hidden"""
 
     def get_row_by_index(self, index):
         """Returns all values for the row at the given index"""
 
-        row, col = self.__index_to_row_col(index)
+        row, col = self.index_to_row_col(index)
         return self.get_row(row)
 
     @check_length
         Returns all values for the column at the given index
         """
 
-        row, col = self.__index_to_row_col(index)
+        row, col = self.index_to_row_col(index)
         return self.get_col(col)
 
     @check_length
     def get_region_by_index(self, index):
         """Returns all values for the region at the given index"""
 
-        row, col = self.__index_to_row_col(index)
+        row, col = self.index_to_row_col(index)
         return self.get_region(row, col)
 
     def get_used(self, row, col):
     def get_used_by_index(self, index):
         """Returns a list of all used values for a row, col, and region"""
 
-        row, col = self.__index_to_row_col(index)
+        row, col = self.index_to_row_col(index)
         return self.get_used(row, col)
 
     def is_valid_value(self, row, col, value):
     def is_valid_value_for_index(self, index, value):
         """Validates a value for the given index"""
 
-        row, col = self.__index_to_row_col(index)
+        row, col = self.index_to_row_col(index)
         return self.is_valid_value(row, col, value)
 
     def fill_square(self, index=0):
         if len(possible) == 0:
             return False
 
-        #print index, possible #, row, col, region
+        #if self.iterations % 50000 == 0: print index, possible #, row, col, region
         random.shuffle(possible)
 
         for new_value in possible:
 
         return False
 
-    def generate(self):
+    def solve(self):
         self.iterations = 0
         self.fill_square(0)
 
-    def __print_grid(self, grid):
+    @requires_solution
+    def print_grid(self, grid):
         """Prints a nicely formatted version of the Sudoku grid"""
 
         field_width = len(str(self.side_length)) + 2
     def print_solution(self):
         """Prints the generated solution nicely formatted"""
 
-        return self.__print_grid(self.solution)
+        return self.print_grid(self.solution)
 
     def print_masked(self):
         """Prints a masked version of the grid"""
 
-        return self.__print_grid(self.masked_grid)
+        return self.print_grid(self.masked_grid)
 
 def main():
-    s = Sudoku(4, difficulty=GOOD_LUCK)
-    s.generate()
-
+    s = Sudoku(difficulty=EASY)
+    s.print_solution()
     s.print_masked()
-    s.print_solution()
 
 if __name__ == '__main__':
     main()