# # Solve sudoku puzzle # import unittest class Cell(object): def __init__(self, row_idx, col_idx): self.row_idx = row_idx self.col_idx = col_idx self.row = None self.col = None self.box = None self.value = None self.candidates = set(range(1,10)) def __str__(self): return "." if self.value is None else "%d"%self.value def description(self): return "cell(%d,%d)" % (self.row_idx+1,self.col_idx+1) # # Group stores 9 cells for a row, column, or a box # class Group(list): def __init__(self, name, row_idx, col_idx): list.__init__(self, [None]*9) self.name = name self.row_idx = row_idx self.col_idx = col_idx class Row(Group): def __init__(self, row_idx): Group.__init__(self, "row", row_idx, 0) def description(self): return "row %d" % (self.row_idx+1) class Column(Group): def __init__(self, col_idx): Group.__init__(self, "col", 0, col_idx) def description(self): return "col %d" % (self.col_idx+1) class Box(Group): def __init__(self, row_idx, col_idx): Group.__init__(self, "box", row_idx, col_idx) def description(self): return "box(%d,%d)" % (self.row_idx+1, self.col_idx+1) class FillIn(): def __init__(self, cell, number): self.cell = cell self.number = number class Board(object): def __init__(self): self.verbose = False self.rows = [ Row(i) for i in range(9) ] self.cols = [ Column(j) for j in range(9) ] self.boxes = Group("boxes",0,0) for i in range(3): for j in range (3): self.boxes[3*i+j] = Box(i,j) for i in range(9): for j in range(9): box = self.boxes[(i/3)*3+(j/3)] cell = Cell(i,j) cell.box = box cell.row = self.rows[i] cell.col = self.cols[j] self.rows[i][j] = self.cols[j][i] = box[(i%3)*3+(j%3)] = cell # self.init_boxes() self.groups = [ box for box in self.boxes ] + self.rows + self.cols self.rules = [ ("cell has 1 candidate", self.cell_has_1_candidate), ("candidate appears once", self.candidate_appears_once), ("box candidates in row/col", self.box_candidates_in_single_row_or_column), ("N candidates in N cells", self.full_multi_cells ) ] # # Run all rules in order. The rules are ordered from the simplest to # the most complex. # If a rule makes a change to the board (fills a cell or removes candidates), # restart the rules from the start. # def solve(self): self.remove_candidates() self.changed = True while self.changed: self.changed = False self.log(self) self.log("new round of rules") for (rule_name, rule) in self.rules: self.log("applying rule: %s" % rule_name ) fill_ins = rule() self.log("solved %d cells" % len(fill_ins)) if len(fill_ins) > 0: for fill_in in fill_ins: self.solve_cell(fill_in.cell, fill_in.number) if self.changed: break self.log("done") # # Rule: if a cell has only one remaining candidate, # then that candidate is the solution for the cell # def cell_has_1_candidate(self): fill_ins = [] for row in self.rows: for cell in row: if cell.value is not None : continue if len(cell.candidates) == 1: number = cell.candidates.pop() self.log("%s has only one candidate #%d" % (cell.description(),number)) fill_ins.append( FillIn(cell=cell, number=number) ) return fill_ins # # Rule: if a candidate appears only once in a row (or column or box), # then that candidate is the solution for its cell # def candidate_appears_once(self): fill_ins = [] for group in self.groups: fills = self.candidate_appears_once_in_group(group) # fill_ins.extend( fills ) if len(fills) > 0: # stop searching to apply simpler rules return fills; return fill_ins def candidate_appears_once_in_group(self, group): map = self.candidates_to_cells_map(group) fill_ins = [ FillIn(cell=map[i][0], number=i) for i in range(1,10) if len(map[i]) == 1 ] if self.verbose: for fillin in fill_ins: self.log("Candidate %d at %s appears only once in %s" % (fillin.number, fillin.cell.description(), group.description()) ) return fill_ins def candidates_to_cells_map(self, group): map = [ [] for i in range(10) ] # item 0 not used for cell in group: if cell.value is None : for candidate in cell.candidates: # candidates are 1-based map[candidate].append(cell) return map # # Rule: If a candidate number appears more than once in one box, # but all the appearances belong to the same row, # then that number cannot appear anywere else along the same row # except in the same box. # The same holds for candidates in the same column def box_candidates_in_single_row_or_column(self): for box in self.boxes: self.box_candidates(box) return [] def box_candidates(self,box): map = self.candidates_to_cells_map(box) for num in range(1,10) : cells = map[num] if len(cells) < 2 : continue row = self.in_same_row( cells ) if row is not None : removed = self.remove_other_candidates( number=num, remove=row, keep=cells ) self.log_row_description( box, num, len(cells), row, removed ) continue col = self.in_same_col( cells ) if col is not None : removed = self.remove_other_candidates( number=num, remove=col, keep=cells ) self.log_col_description( box, num, len(cells), col, removed ) def in_same_row(self,cells): row = cells[0].row for cell in cells: if cell.row != row: return None return row def in_same_col(self,cells): col = cells[0].col for cell in cells: if cell.col != col: return None return col def remove_other_candidates(self, number, remove, keep ): removed = [] for cell in remove: if cell.value is None and cell not in keep: if number in cell.candidates : cell.candidates.remove( number ) removed.append( cell ) self.changed = True return removed def log_row_description(self, box, num, times, row, removed ): if( self.verbose and len(removed) > 0 ): self.log( ( "Candidate %d appears %d times in %s, but only in %s. " + "Removed it from column(s) %s in the row." ) % ( num, times, box.description(), row.description(), ",".join([str(cell.col_idx+1) for cell in removed]) ) ) def log_col_description(self, box, num, times, col, removed ): if( self.verbose and len(removed) > 0 ): self.log( ( "Candidate %d appears %d times in %s, but only in %s. " + "Removed it from rows(s) %s in the column." ) % ( num, times, box.description(), col.description(), ",".join([str(cell.row_idx+1) for cell in removed]) ) ) # # Rule: Find two numbers that appear in exactly two cells within a row, # column, or a box. No other numbers have space to share these two cells. # Eliminate them (the "stragglers"). # Continue finding tree numbers in three cells, and so on. # def full_multi_cells(self): for n in range(2,10): for group in self.groups: (cells, numbers) = self.find_n_numbers_in_n_cells( group, n ) if len(cells) > 0: removed = self.remove_stragglers( numbers=numbers, cells=cells ) self.log_multi_cells_description(n,numbers,cells,removed,group) if self.changed: return [] # Stop searching to re-run easier rules return [] # Remove all candidates except the ones listed in 'numbers' def remove_stragglers(self, numbers, cells ): removed = {} # hash of cell:[array of removed candidates from the cell] for cell in cells: for candidate in cell.candidates.copy(): if candidate not in numbers: if cell not in removed: removed[cell] = [] removed[cell].append(candidate) cell.candidates.remove( candidate ) self.changed = True return removed def find_n_numbers_in_n_cells(self, group, n): map = self.candidates_to_cells_map(group) numbers_appearing_n_times = filter( lambda i : len(map[i]) == n, range(1,10) ) if len( numbers_appearing_n_times ) < n : return ( [], [] ) if ( len( numbers_appearing_n_times ) == n and self.all_cell_sets_equal( numbers_appearing_n_times, map ) ): return ( map[numbers_appearing_n_times[0]], numbers_appearing_n_times ) # # If there are four numbers that appear in two cells each, # We will check all possible pairs for subset_of_n in self.all_subsets( set(numbers_appearing_n_times), n ): if self.all_cell_sets_equal( subset_of_n, map ): for i in subset_of_n: # Just get a random number from subset_of_n return (map[i],subset_of_n) return ( [], [] ) def all_subsets(self,a_set,n): # Yields all subsets of length n if len(a_set) < n: return if len(a_set) ==n: yield a_set return if n == 1: for elt in a_set: yield set([elt]) else: c = a_set.copy() while len(c) > 0 : elt = c.pop() for s in self.all_subsets( c, n-1 ): yield s.union([elt]) def all_cell_sets_equal(self, numbers, numbers_to_cells_map): set0 = None for i in numbers: if set0 is None: set0 = set(numbers_to_cells_map[i]) elif set0 != set(numbers_to_cells_map[i]): return False return True def log_multi_cells_description(self,n,numbers,cells,removed,group): if( len(removed)>0 and self.verbose ): self.log(self.full_multi_cells_description(n,numbers,cells,removed,group)) def full_multi_cells_description(self,n,numbers,cells,removed,group): numbers_text = ",".join( str(number) for number in numbers ) cells_text = ",".join( cell.description() for cell in cells ) removed_text=", ".join([ "%s from %s" % ( ",".join([str(num) for num in removed[cell]]) , cell.description()) for cell in removed ]) return(("In %s, %d candidates, %s, appear in %d cells, %s. "+ "Removed stragglers %s.") % (group.description(),n,numbers_text, n, cells_text, removed_text) ) # # Utilities # # # Fill a number into a cell, then remove that number from possible # candidates in the same row, column, and box # def solve_cell(self, cell, value): self.log("solve %s = %d" % (cell.description(),value)) self.changed = True cell.value = value self.remove_candidates_for_cell( cell ) def remove_candidates(self): fill_ins = [] for row in self.rows: for cell in row: if cell.value is None : continue fill_ins.extend( self.remove_candidates_for_cell(cell) ) return fill_ins def remove_candidates_for_cell(self, cell): self.remove_candidates_in_group( cell.value, cell.row ) self.remove_candidates_in_group( cell.value, cell.col ) self.remove_candidates_in_group( cell.value, cell.box ) return [] def remove_candidates_in_group( self, value, group ): for cell in group: if cell.value is not None : continue if value in cell.candidates: cell.candidates.remove(value) self.changed = True def __str__(self): return "\n".join([ self.row_to_string(row) + ("","\n")[row[0].row_idx%3==2] for row in self.rows ]) def row_to_string(self,row): return "".join([ cell.__str__() + (""," ")[cell.col_idx%3==2] for cell in row ]) def detailed_description(self): box_line = " +" + ("-"*17 + "+")*3 cell_line = " |" + (" "*17 + "|")*3 lines = [] for box_x in range(3): for cell_x in range(3*box_x, 3*box_x+3): lines.append((cell_line, box_line)[cell_x % 3 == 0]) for x in range(3): line = "" for box_y in range(3): for cell_y in range(3*box_y, 3*box_y+3): line+=(" "," | ")[cell_y%3 == 0] for y in range(3): cell = self.rows[cell_x][cell_y] if cell.value is not None: line+= (" ",str(cell.value))[x == 1 and y == 1] else: candidate = 3*x+y+1 line+=(".",str(candidate))[candidate in cell.candidates] line +=" |" lines.append(line) lines.append(box_line) return "\n".join(lines) def init_from_string(self, str): row = 0 col = 0 for char in str: if( char == "." ): col+=1 continue if( char >= "0" and char <= "9" ): if col >= 9: raise Exception("Expected 9 elements in row %d, but got %d" % (row+1,col+1)) number = ord(char)-ord("0") self.solve_cell( self.rows[row][col], number ) col+=1 continue if( char == "\n" ): if col == 0: # Ignore empty lines continue if col != 9: raise Exception("Expected 9 elements in row %d, but got %d" % (row+1,col+1)) col=0 row+=1 if( row == 9 ): break if( row != 9 or col != 0 ): raise Exception("Incomplete board: %d rows, %d columns" % (row+1,col+1)) def log(self, str): if self.verbose: print str #------------------------------------------------------------------------------ # # Unit Tests # #------------------------------------------------------------------------------ class TestBoard(unittest.TestCase): def setUp(self): self.board = Board() def test_remove_candidates_in_group(self): group = [ Cell(0,1), Cell(0,2), Cell(0,3) ] self.assertEqual( group[0].candidates, set(range(1,10)) ) self.assertEqual( group[1].candidates, set(range(1,10)) ) self.assertEqual( group[2].candidates, set(range(1,10)) ) self.board.remove_candidates_in_group( 3, group ) self.assertEqual( group[0].candidates, set([1,2, 4,5,6,7,8,9]) ) self.assertEqual( group[1].candidates, set([1,2, 4,5,6,7,8,9]) ) self.assertEqual( group[2].candidates, set([1,2, 4,5,6,7,8,9]) ) self.board.remove_candidates_in_group( 3, group ) self.assertEqual( group[0].candidates, set([1,2, 4,5,6,7,8,9]) ) self.board.remove_candidates_in_group( 5, group ) self.assertEqual( group[0].candidates, set([1,2, 4, 6,7,8,9]) ) def test_candidate_appears_once_in_group(self): group = [ Cell(0,1), Cell(0,2), Cell(0,3), Cell(0,4) ] group[3].value = 7 group[0].candidates &= set([1, 3,4]) group[1].candidates &= set([ 2,3 ]) # <- 2 is the only value that appears only once group[2].candidates &= set([1, 3,4]) group[3].candidates &= set([1,2,3,4]) # <- this does not count because value is set fill_ins = self.board.candidate_appears_once_in_group( group ) self.assertEqual( len(fill_ins), 1 ) fill_in = fill_ins[0] self.assertEqual( (fill_in.cell, fill_in.number), ( group[1], 2 ) ) def test_in_same_row(self): board = self.board rows = board.rows row = self.board.in_same_row( [ rows[3][1], rows[3][5], rows[3][8] ]) self.assertEqual( row, rows[3] ) row = self.board.in_same_row( [ rows[3][1], rows[6][5], rows[3][8] ]) self.assertEqual( row, None ) row = self.board.in_same_row( [ rows[4][1] ]) self.assertEqual( row, rows[4] ) def test_all_cell_sets_equal(self): rows = self.board.rows c1, c2, c3 = rows[3][1], rows[7][5], rows[3][8] numbers = [1,2,3] numbers_to_cells_map = { 1: [c1,c2,c3], 2: [c2,c3,c1], 3: [c3,c1,c2] } eq = self.board.all_cell_sets_equal( numbers, numbers_to_cells_map ) self.assertEqual( eq, True ) numbers_to_cells_map = { 1: [c1,c2,c3], 2: [c2,c3,c1], 3: [c3,c2] } eq = self.board.all_cell_sets_equal( numbers, numbers_to_cells_map ) self.assertEqual( eq, False ) def test_candidates_to_cells_map(self): cell1 = Cell(0,1); cell1.candidates = [1] cell2 = Cell(0,2); cell2.candidates = [5,6,7] cell3 = Cell(0,3); cell3.candidates = [1,2,3] cell4 = Cell(0,4); cell4.candidates = [2,4] cell5 = Cell(0,5); cell5.candidates = [1,2,5,6,7] cell6 = Cell(0,6); cell6.candidates = [7] group = [cell1,cell2,cell3,cell4,cell5,cell6] expected_map = [[], [cell1,cell3,cell5], #1 [cell3,cell4,cell5], #2 [cell3], #3 [cell4], #4 [cell2,cell5], #5 [cell2,cell5], #6 [cell2,cell5,cell6], #7 [], #8 [], #9 ] map = self.board.candidates_to_cells_map( group ) self.assertEqual( expected_map, map ) def test_find_n_numbers_in_n_cells_1(self): cell1 = Cell(0,1); cell1.candidates = [1] cell2 = Cell(0,2); cell2.candidates = [5,6,7] # <-- 5 and 6 cell3 = Cell(0,3); cell3.candidates = [1,2,3] cell4 = Cell(0,4); cell4.candidates = [2,4] cell5 = Cell(0,5); cell5.candidates = [1,2,5,6,7] # <-- 5 and 6 cell6 = Cell(0,6); cell6.candidates = [7] group = [cell1,cell2,cell3,cell4,cell5,cell6] cells, numbers = self.board.find_n_numbers_in_n_cells( group, 2 ) self.assertEqual( set(numbers), set([5,6]) ) self.assertEqual( set(cells), set([cell2,cell5]) ) def test_find_n_numbers_in_n_cells_2(self): cell1 = Cell(0,1); cell1.candidates = [1] # #1 appears twice cell2 = Cell(0,2); cell2.candidates = [5,6,7] # <-- 5 and 6 cell3 = Cell(0,3); cell3.candidates = [2,3] cell4 = Cell(0,4); cell4.candidates = [2,4] cell5 = Cell(0,5); cell5.candidates = [1,2,5,6,7] # <-- 5 and 6 cell6 = Cell(0,6); cell6.candidates = [7] group = [cell1,cell2,cell3,cell4,cell5,cell6] cells, numbers = self.board.find_n_numbers_in_n_cells( group, 2 ) self.assertEqual( set(numbers), set([5,6]) ) self.assertEqual( set(cells), set([cell2,cell5]) ) def test_find_n_numbers_in_n_cells_3(self): cell1 = Cell(0,1); cell1.candidates = [1] # 1 appears twice cell2 = Cell(0,2); cell2.candidates = [5,7] # 5 appears twice cell3 = Cell(0,3); cell3.candidates = [2,3] cell4 = Cell(0,4); cell4.candidates = [2,4] cell5 = Cell(0,5); cell5.candidates = [1,2,5,7] # 5 appears twice cell6 = Cell(0,6); cell6.candidates = [7] group = [cell1,cell2,cell3,cell4,cell5,cell6] cells, numbers = self.board.find_n_numbers_in_n_cells( group, 2 ) self.assertEqual( numbers, [] ) self.assertEqual( cells, [] ) def test_all_subsets(self): subsets = [ subset for subset in self.board.all_subsets( set([99]), 1 ) ] self.assertEqual( subsets, [set([99])] ) subsets = [ subset for subset in self.board.all_subsets( set([1,2,3]), 1 ) ] self.assertEqual( subsets, [set([1]), set([2]), set([3])] ) subsets = [ subset for subset in self.board.all_subsets( set([1,2,3]), 3 ) ] self.assertEqual( subsets, [set([1,2,3])] ) subsets = [ subset for subset in self.board.all_subsets( set([1,2,3]), 2 ) ] self.assertEqual( subsets, [set([1,2]), set([1,3]), set([2,3])] ) def test_remove_stragglers(self): cell1 = Cell(0,1); cell1.candidates = set([1]) # #1 appears twice cell2 = Cell(0,2); cell2.candidates = set([5,6,7]) # <-- 5 and 6 cell3 = Cell(0,3); cell3.candidates = set([2,3]) cell4 = Cell(0,4); cell4.candidates = set([2,4]) cell5 = Cell(0,5); cell5.candidates = set([1,2,5,6,7]) # <-- 5 and 6 cell6 = Cell(0,6); cell6.candidates = set([7]) group = [cell1,cell2,cell3,cell4,cell5,cell6] cells = [cell2, cell5] numbers = [5,6] self.board.remove_stragglers( numbers=numbers, cells=cells ) self.assertEqual(cell1.candidates, set([1])) self.assertEqual(cell2.candidates, set([5,6])) # <--- 7 removed self.assertEqual(cell3.candidates, set([2,3])) self.assertEqual(cell4.candidates, set([2,4])) self.assertEqual(cell5.candidates, set([5,6])) # <--- 1,2,7 removed self.assertEqual(cell6.candidates, set([7])) def test_remove_other_candidates(self): cell1 = Cell(0,1); cell1.candidates = set([1]) cell2 = Cell(0,2); cell2.candidates = set([5,6,7]) cell3 = Cell(0,3); cell3.candidates = set([2,3]) # 2, keep this cell4 = Cell(0,4); cell4.candidates = set([2,4]) # 2, keep this cell5 = Cell(0,5); cell5.candidates = set([1,2,5,6,7]) # 2, remove this cell6 = Cell(0,6); cell6.candidates = set([7]) group = [cell1,cell2,cell3,cell4,cell5,cell6] cells = [cell3, cell4] self.board.remove_other_candidates( number=2, remove=group, keep=cells ) self.assertEqual(cell1.candidates, set([1])) self.assertEqual(cell2.candidates, set([5,6,7])) self.assertEqual(cell3.candidates, set([2,3])) # kept 2 self.assertEqual(cell4.candidates, set([2,4])) # kept 2 self.assertEqual(cell5.candidates, set([1,5,6,7])) # <--- 2 removed self.assertEqual(cell6.candidates, set([7])) def test_full_multi_cells_description(self): n = 2 numbers = [2,5] cell1 = self.board.rows[2][4] cell2 = self.board.rows[2][5] cells = [ cell1, cell2 ] removed = { cell1 : [1,3,4], cell2 : [7] } group = self.board.boxes[1] result = self.board.full_multi_cells_description(n,numbers,cells,removed,group) expected = ( "In box(1,2), 2 candidates, 2,5, appear in 2 cells, cell(3,5),cell(3,6). " + "Removed stragglers 1,3,4 from cell(3,5), 7 from cell(3,6)." ) self.assertEqual(expected, result) # # # def solveSudoku( puzzle ): board = Board() board.verbose = True board.init_from_string( puzzle ) print print "Puzzle is:\n", board board.solve() print "Solution is:\n", board return board if __name__ == "__main__": puzzle = """ .5...12.9 .6.29.... 4...6.... 8.....4.1 .73...... ..4...... ......6.4 ..5...... 7...8...2 """ hard = """ ..9 6.. ..8 ... ..7 .53 3.2 8.5 ..9 .2. 3.. 5.. 9.. ... ..2 ..8 ..2 .4. 8.. 2.6 9.4 65. 1.. ... 2.. ..3 6.. """ easy = """ .1. 5.. .47 ... ... 98. ... 2.6 ..3 .38 .2. 6.1 2.. .5. ..9 9.1 .3. 47. 1.. 8.2 ... .97 ... ... 32. ..5 .6. """ hard2 = """ .9. .26 ... 183 9.. ... 7.2 1.. 4.. ... ..5 ..4 .18 ... 65. 2.. 8.. ... ..1 ..3 7.2 ... ..9 361 ... 27. .4. """ # hard2="_9__26___+1839____6+7621_84__+_7___5__4+_18__265_+2__8_____+__1__37_2+_27__9361+_3_271_4_" run_unit_tests = False if( run_unit_tests ): unittest.main() else: solution = solveSudoku( hard2 )