Commits

Charlie Arnold committed 14bdb3d

can solve puzzles that require no backtracking/guessing (all puzzles except snail.*)

Comments (0)

Files changed (1)

             if (rowi + 1) % 3 == 0:
                 rows.append(border)
         return '\n'.join(rows)
+    
+    def solveCertain(self):
+        ''' Solve as much of the puzzle as we can with certainty
+        '''
+        
+        while True:
+            foundClosedSet = False
+            for grpList in (self.rowGroups, self.colGroups, self.sqrGroups):
+                for grp in grpList:
+                    for cellset in grp.findClosedSets():
+                        foundClosedSet = True
+                        closedSetVals = iter(cellset).next().possibles
+                        uncertainCells = set(c for c in grp.cells if c.certainty < 1)
+                        for cell in uncertainCells.difference(cellset):
+                            if cell.certainty < 1: # could be changed from previous exclusions
+                                cell.excludeVals(closedSetVals)
+            if not foundClosedSet:
+                break
 
 
 class CellGroup(object):
     def _addCell(self, cell):
         self.cells.append(cell)
     
-    def findExclusives(self):
-        'Find cells that contain all of a certain set of values'
-        cells = list(self.cells)
-        for i, c in enumerate(cells):
-            cl = [test for test in cells[i:]
-                  if test.possibles == c.possibles]
+    def findClosedSets(self):
+        ''' Find sets of cells with the same list of possibles where
+              len(possibles) == len(setOfCells) ..
+            Where this is true, we know that no other cells in the
+              group can have those values.
+        '''
+        
+        closedsets = []
+        cells = set([c for c in self.cells if c.certainty < 1])
+        while len(cells) > 0:
+            testc = cells.pop()
+            cs = set([testc])
+            cs.update([c for c in cells
+                       if testc.possibles == c.possibles])
+            if len(cs) not in (1, 9) and len(cs) == len(testc.possibles):
+                closedsets.append(cs)
+            cells.difference_update(cs)
+        
+        return closedsets
+
 
 class RowCellGroup(CellGroup):
     pass
     
     logging.basicConfig(level=logging.INFO)
     pzl = SudokuPuzzle()
-    pzl.initFromBinFile(p.join(testd, '11-1.in'))
+    pzl.initFromBinFile(p.join(testd, 'snail2.in'))
+    logging.info(' Result: \n%s'% pzl)
+    pzl.solveCertain()
     logging.info(' Result: \n%s'% pzl)
     
     
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.