Commits

Josh VanderLinden  committed 14951fa

Initial import

I'm in the process of adding some new features, so this version might be broken.

  • Participants

Comments (0)

Files changed (3)

+syntax: glob
+*.pyc
+*.swp
+

File sudokulib/__init__.py

Empty file added.

File sudokulib/sudoku.py

+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+"""
+A simple backtracking Sudoku generator
+"""
+
+from copy import copy
+from curses.wrapper import wrapper
+from pprint import pprint
+import curses
+import math
+import random
+import time
+
+MIN = -1
+EASY = 0
+MEDIUM = 1
+HARD = 2
+EXPERT = 3
+INSANE = 4
+GOOD_LUCK = 5
+
+# ------------------- decorators ------------------
+
+def check_length(func):
+    """Ensures that the provided list of values has a valid length"""
+
+    def wrapped(self, num, values):
+        if len(values) == self.side_length:
+            return func(self, num, values)
+        else:
+            raise ValueError('Invalid values.  Please specify a list of %i values.' % self.side_length)
+    return wrapped
+
+# ------------------- Sudoku --------------------
+
+class Sudoku(object):
+    SCALE =  {
+        MIN: 0.50,
+        EASY: 0.40,
+        MEDIUM: 0.35,
+        HARD: 0.30,
+        EXPERT: 0.24,
+        INSANE: 0.17,
+        GOOD_LUCK: 0.12,
+    }
+
+    def __init__(self, grid_size=3, difficulty=MEDIUM):
+        self.set_grid_size(grid_size)
+        self.set_difficulty(difficulty)
+        self.side_length = self.grid_size ** 2
+        self.square = self.side_length ** 2
+        self.possibles = set([i + 1 for i in range(self.side_length)])
+        self.solution = []
+        self._masked = None
+        self.iterations = 0
+
+        self.clear()
+
+    def set_grid_size(self, grid_size):
+        self.grid_size = grid_size
+
+    def set_difficulty(self, difficulty):
+        self.difficulty = difficulty
+
+    def get_row(self, row):
+        """Returns all values for the specified row"""
+
+        start = row * self.side_length
+        end = start + self.side_length
+        return self.solution[start:end]
+
+    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)
+        return self.get_row(row)
+
+    @check_length
+    def set_row(self, row, values):
+        """Sets the values for the specified row"""
+
+        start = row * self.side_length
+        end = start + self.side_length
+        self.solution[start:end] = values
+
+    def get_col(self, col):
+        """Returns all values for the specified column"""
+
+        return self.solution[col::self.side_length]
+
+    def get_col_by_index(self, index):
+        """
+        Returns all values for the column at the given index
+        """
+
+        row, col = self.__index_to_row_col(index)
+        return self.get_col(col)
+
+    @check_length
+    def set_col(self, col, values):
+        """Sets the values for the specified column"""
+
+        self.solution[col::self.side_length] = values
+
+    def get_region(self, row, col):
+        """Returns all values for the region at the given (row, col)"""
+
+        start_row = int(row / self.grid_size) * self.grid_size
+        start_col = int(col / self.grid_size) * self.grid_size
+
+        values = []
+        for i in range(self.grid_size):
+            start = (start_row + i) * self.side_length + start_col
+            end = start + self.grid_size
+            values.extend(self.solution[start:end])
+
+        return values
+
+    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)
+        return self.get_region(row, col)
+
+    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):
+        """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):
+        """Translates an index in our 1-dimensional list to a (row, col)"""
+
+        return divmod(index, self.side_length)
+
+    def get_used(self, row, col):
+        """Returns a list of all used values for a row, column, and region"""
+
+        r = self.get_row(row)
+        c = self.get_col(col)
+        region = self.get_region(row, col)
+
+        return (r + c + region)
+
+    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)
+        return self.get_used(row, col)
+
+    def is_valid_value(self, row, col, value):
+        """
+        Validates whether or not a value will work in the grid, without using
+        the pre-generated solution
+        """
+
+        return value not in self.get_used(row, col)
+
+    def fill_square(self, index=0):
+        """
+        Recursively populates each square on the Sudoku grid until a solution
+        is found.  Most of this method was inspired by Jeremy Brown
+        """
+
+        if self.solution[index]:
+            if index + 1 >= self.square:
+                return True
+            return self.fill_square(index + 1)
+
+        used = self.get_used_by_index(index)
+        possible = list(self.possibles.difference(used))
+        if len(possible) == 0:
+            return False
+
+        #print index, possible #, row, col, region
+        random.shuffle(possible)
+
+        for new_value in possible:
+            self.solution[index] = new_value
+            self.iterations += 1
+
+            if index + 1 >= self.square or self.fill_square(index + 1):
+                return True
+
+            self.solution[index] = None
+
+        return False
+
+    def generate(self):
+        self.iterations = 0
+        self.fill_square(0)
+
+    @property
+    def masked_grid(self):
+        """Generates and caches a Sudoku with several squares hidden"""
+
+        if self._masked is None:
+            self._masked = copy(self.solution)
+            min = math.ceil(Sudoku.SCALE[self.difficulty] * self.square)
+            max = math.ceil(Sudoku.SCALE.get(self.difficulty - 1, min) * self.square)
+            numbers_to_show = random.randint(min, max)
+
+            uncleared_squares = [i for i in range(len(self.solution))]
+            for i in range(self.square - numbers_to_show):
+                index = random.choice(uncleared_squares)
+                self._masked[index] = '_'
+                uncleared_squares.remove(index)
+
+        return self._masked
+
+    def print_solution(self):
+        """
+        Prints the generated solution nicely formatted
+        """
+
+        print 'Required %i iterations' % self.iterations
+        return self.__print_grid(self.solution)
+
+    def print_masked(self):
+        """
+        Prints a masked version of the grid
+        """
+
+        return self.__print_grid(self.masked_grid)
+
+    def __print_grid(self, grid):
+        """
+        Prints a nicely formatted version of the Sudoku grid
+        """
+
+        field_width = len(str(self.side_length)) + 2
+        format = ''.join(['%s' for i in range(self.grid_size)])
+        format = '|'.join([format for i in range(self.grid_size)])
+
+        for row in range(self.side_length):
+            start = row * self.side_length
+            end = start + self.side_length
+            values = tuple(str(val).center(field_width) for val in grid[start:end])
+            print format % values
+
+            # print a dividing line for each set of regions
+            if row < self.side_length - 1 and (row + 1) % self.grid_size == 0:
+                print '+'.join('-' * field_width * self.grid_size for i in range(self.grid_size))
+
+def main():
+    s = Sudoku(difficulty=GOOD_LUCK)
+    s.generate()
+    s.print_masked()
+    s.print_solution()
+
+if __name__ == '__main__':
+    main()
+