""" Sudoku: module to model and solve ancient Japanese newspaper puzzles. Add numbers to a grid such that no value is used twice in any row, column, or (normally) three by three square. For example: 1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 3 4 5 6 7 8 9 1 5 6 7 8 9 1 2 3 4 8 9 1 2 3 4 5 6 7 3 4 5 6 7 8 9 1 2 6 7 8 9 1 2 3 4 5 9 1 2 3 4 5 6 7 8 For normal use: import Sudoku s = Sudoku([ "123456789", "456789123", "789123456", "234567891", "5678 1234", "891234567", "345678912", "678912345", "912345678" ]) print s.solution().string() """ __revision__ = 1 import sets import copy class SudokuException(Exception): """ If something has gone wrong--if the sudoku puzzle is invalid or if no solution can be found, for example--then a SudokuException is raised. """ pass class Sudoku(object): """ Class to model Sudoku puzzles. """ def __init__( self, row_col, square=3, num_square=3, min_val=1, max_val=9 ): """ row_col is an array of arrays, like [ " " for i in range( 9 ) ] There are several untested options: square: the size of an individual square, by default 3 num_square: the number of squares wide, by default 3 min_val: the first allowable value, by default 1 max_val: the last allowable value, by default 9 """ self.square = square self.num_square = num_square self.row_size = self.square * self.num_square self.col_size = self.row_size self.min_val = min_val self.max_val = max_val if len(row_col) != self.row_size: raise SudokuException( 'Not the right number of rows' ) self.rows = [] for row in row_col: out_row = [] if len(row) != self.col_size: raise SudokuException( 'Not the right number of cols' ) for elt in row: if elt == None or str(elt) == ' ': out_row.append( None ) else: out_row.append( int( elt ) ) self.rows.append( out_row ) self.possibilities = [ [ None for j in range( self.col_size ) ] for i in range( self.row_size ) ] self._init_possibilities() self.verify() self._full_count() def _init_possibilities( self ): """ The internal structure 'possibilities' holds a set of possible values that could be used for each element in self.rowcol . This structure is updated when add_val() is called. """ # rows for i in range( self.row_size ): row_vals = self._unused_values( self.get_row( i )) for j in range( self.col_size ): if self.rows[i][j] == None: self.possibilities[i][j] = sets.Set( row_vals ) else: self.possibilities[i][j] = sets.Set() # cols for j in range( self.col_size ): col_vals = self._unused_values( self.get_col( i )) col_set = sets.Set( col_vals ) for i in range( self.row_size ): self.possibilities[i][j].intersection( col_set ) # squares for square_row in range( self.square ): for square_col in range( self.square ): square_list = self.get_square( square_row, square_col ) square_vals = self._unused_values( square_list ) square_set = sets.Set( square_vals ) i_base = square_row * self.square j_base = square_col * self.square for i_offset in range( self.square ): for j_offset in range( self.square ): i = i_base + i_offset j = j_base + j_offset self.possibilities[i][j].intersection( square_set ) def __cmp__( self, otro ): """ Two Sudoku squares are equal if their rowcol structs have the same value, row-by-row then col-by-col. If they don't have the same size, don't compare them. """ if (self.row_size != otro.row_size or self.col_size != otro.col_size): return SudokuException('you compared two sudokus of the wrong size') for i in range( self.row_size ): for j in range( self.col_size ): val = cmp( self.rows[i][j], otro.rows[i][j] ) if val != 0: return val return 0 def clone( self ): """ Cheaply copy with copy.deepcopy() """ new = Sudoku( row_col=self.rows, square=self.square, num_square=self.num_square, min_val=self.min_val, max_val=self.max_val ) return new def _full_count( self ): """ Count number of elements and store in self.num_full """ self.num_full = 0 for i in range( self.row_size ): for j in range( self.col_size ): if self.rows[i][j] != None: self.num_full += 1 def full( self ): """ Return 'True' if there are no remaining possibilities (there are no empty elements). """ return self.num_full >= self.row_size * self.col_size def num_nonempty( self ): """ Return count of non-empty elements. """ num_full = 0 for i in range( self.row_size ): for j in range( self.row_size ): if self.rows[i][j] != None: num_full += 1 return num_full def _verify_list( self, test_list ): """ For an arbitrary list, make sure no values are repeated. """ seen = {} for val in test_list: if val == None: continue elif val < self.min_val: raise SudokuException('value %d is too small' % val ) elif val > self.max_val: raise SudokuException('value %d is too large' % val ) elif seen.has_key( val ): raise SudokuException('value %d already seen' % val ) else: seen[val] = 1 return True def _list_num_none( self, test_list ): """ For an arbitrary list, return number that are 'None'. """ count = 0 for elt in test_list: if elt == None: count += 1 return count def _list_num_not_none( self, test_list ): """ For an arbitrary list, return number that are not 'None'. """ return len(test_list) - self._list_num_none( test_list ) def _unused_values( self, test_list ): """ For an arbitrary list, a list of values from min_val to max_val that are not in that list. """ unused_values = [] for i in range( self.min_val, self.max_val + 1 ): if i not in test_list: unused_values.append( i ) return unused_values def get_row( self, row_num ): """ Get 'row_num'th row of puzzle. """ return [ self.rows[row_num][j] for j in range( self.col_size ) ] def get_rows( self ): """ Get all rows of puzzle. """ return [ self.get_row( i ) for i in range( self.row_size ) ] def get_col( self, col_num ): """ Get 'col_num'th column of puzzle. """ return [ self.rows[i][col_num] for i in range( self.row_size ) ] def get_cols( self ): """ Get all columns of puzzle. """ return [ self.get_col( j ) for j in range( self.col_size ) ] def get_square( self, square_row, square_col ): """ Assuming each square is self.square x self.square, get the 'square_row'th square in the row, and get the 'square_col'th square in the column. For example, given 1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 3 4 5 6 7 8 9 1 5 6 7 8 9 1 2 3 4 8 9 1 2 3 4 5 6 7 3 4 5 6 7 8 9 1 2 6 7 8 9 1 2 3 4 5 9 1 2 3 4 5 6 7 8 square_row=1, square_col=1 gets 5 6 7 8 9 1 2 3 4 """ square_list = [] i_base = square_row * self.square j_base = square_col * self.square for i_offset in range( self.square ): i = i_base + i_offset for j_offset in range( self.square ): j = j_base + j_offset square_list.append( self.rows[i][j] ) return square_list def get_squares( self ): """ Get a list of each square in puzzle. """ squares = [] for square_row in range( self.num_square ): for square_col in range( self.num_square ): squares.append( self.get_square( square_row, square_col ) ) return squares def verify( self ): """ Make sure the puzzle is valid. """ for row in self.get_rows(): self._verify_list( row ) for col in self.get_cols(): self._verify_list( col ) for square in self.get_squares(): self._verify_list( square ) # now check possibilities # TODO: better validation here for i in range( self.row_size ): for j in range( self.col_size ): if ( self.rows[i][j] == None and len( self.possibilities[i][j] ) < 1 ): raise SudokuException('not enough possibilities for row ') def add_val( self, row, col, val): """ Add the value 'val' at position row x col. """ if self.rows[row][col] == None: self.num_full += 1 self.rows[row][col] = val self.verify() # remove all possibilities for this elt self.possibilities[row][col] = sets.Set() # remove possibility from row for j in range( self.col_size ): self.possibilities[row][j].discard( val ) # remove possibility from col for i in range( self.row_size ): self.possibilities[i][col].discard( val ) # remove possibility from square square_row = row // self.square square_col = col // self.square i_base = square_row * self.square j_base = square_col * self.square for i_offset in range( self.square ): for j_offset in range( self.square ): i = i_base + i_offset j = j_base + j_offset self.possibilities[i][j].discard( val ) return self def _string_list( self, test_list ): """ Convert a list into a string. 'None' values are converted into a single space. Ints are converted into strings. Only works well for single-digit values. """ out_string = "" for val in test_list: if val == None: val = ' ' out_string += str( val ) return out_string def strings( self ): """ Return a list of strings, one to represent each row. """ return [ self._string_list( row ) for row in self.get_rows() ] def string( self ): """ Return a string (with embedded newlines) to represent the puzzle. """ out_string = '' for string in self.strings(): out_string += string + '\n' return out_string def get_possibility( self ): """ Find the first row and column with possible values. Return the tuple ( i, j, set ) where i and j are the offsets in self.rows and 'set' is the set of allowed values for self.rows[i][j]. """ for i in range( self.row_size ): for j in range( self.col_size ): p_set = self.possibilities[i][j] if len(p_set) > 0: return ( (i, j, p_set) ) def fill_out( self ): """ Find empty positions in the puzzle with only one possibility. If any are found, fill them in and call fill_out again. """ changed = False for i in range( self.row_size ): for j in range( self.col_size ): p_set = self.possibilities[i][j] if len( p_set ) == 1: rowcol_val = p_set.pop() self.add_val( i, j, rowcol_val ) changed = True if changed == True: self.fill_out() def _num_solved( self ): """ Return a heuristic representing how "solved" the puzzle is. FIXME: this really just returns num_nonempty()*3. """ left = 0 for row in self.get_rows(): left += self._list_num_not_none( row ) for col in self.get_cols(): left += self._list_num_not_none( col ) for square in self.get_squares(): left += self._list_num_not_none( square ) return left # TODO: add an iterator for finding all solutions # TODO: add an iterator for finding all sub-possibilities def solution( self ): """ Find a valid, full puzzle solution for the given puzzle. Although this code is relatively clean-looking, it's not very efficient right now. Code uses a FIFO stack to find and process potential solutions. It could easily be extended to use a heuristic like _num_solved(). """ p_queue = [ ( 0, self ) ] while len(p_queue): ( left, this ) = p_queue.pop() if this.full(): return this i, j, p_list = this.get_possibility() # print '[%d] %d %d' % ( len( p_queue ) , i, j ) for p_elt in p_list: new_sudoku = this.clone() try: new_sudoku.fill_out() new_sudoku.add_val( i, j, p_elt ) p_queue.insert( 0, (0, new_sudoku) ) except SudokuException: continue