Created
December 13, 2008 07:34
-
-
Save bryanwoods/35422 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python | |
# encoding: utf-8 | |
# sudoku-solver version 3 | |
# | |
# Some ideas ripped-off from: | |
# http://www.linuxjournal.com/article/8729 | |
# http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/440542 | |
# Pavol solver in | |
# http://groups.google.com/group/comp.lang.python/browse_thread/thread/5087890f4c5e770d | |
# | |
# Copyright 2005 Ago, | |
# But you are free to copy, reuse, modify and distribute the code as you see fit | |
#!/usr/bin/env python | |
""" | |
untitled.py | |
Created by Bryan Woods on 2008-12-13. | |
Copyright (c) 2008 __Wilson Colab__. All rights reserved. | |
""" | |
from copy import deepcopy | |
class DeadEnd(Exception): pass | |
class Matrix: | |
def __init__(self, input): | |
self.rows = [[] for i in range(9)] | |
self.cols = [[] for i in range(9)] | |
self.submatrices = [[] for i in range(9)] | |
self.cells = [Cell(i,self) for i in range(81)] | |
self.subdiagonals = [self.rows[i][j+i%3] for i in range(9) for j in [0,3,6]] | |
input = [s not in '-*' and int(s) or 0 for s in input if s in '0123456789-*'] | |
for cell,val in zip(self.cells, input): | |
if val: cell.setSolution(val) | |
def solve(self): #Brute-force solver | |
self.solveByReduction() | |
lensols=[(len(c.solutions),c.index) for c in self.cells if not c.solved] | |
if not lensols: return True | |
unsolved = min(lensols)[1] | |
solutions = list(self.cells[unsolved].solutions) | |
for s in solutions: | |
tmpmatrix = deepcopy(self) | |
try: | |
tmpmatrix.cells[unsolved].setSolution(s) | |
if tmpmatrix.solve(): | |
self.update(tmpmatrix) | |
return True | |
except DeadEnd: pass | |
def solveByReduction(self): | |
while True: | |
self.changed = False | |
for c in self.cells: c.solve() | |
for c in self.subdiagonals: c.skim() | |
if not self.changed: break | |
def update(self, m): | |
self.rows, self.cols, self.submatrices, self.cells, self.subdiagonals=\ | |
m.rows, m.cols, m.submatrices, m.cells, m.subdiagonals | |
def __str__(self): | |
return "\n".join(str([c for c in row ])[1:-1] for row in self.rows) | |
class Cell: | |
def __init__(self, index, matrix): | |
self.solved = False | |
self.matrix = matrix | |
self.index = index | |
self.row = matrix.rows[index/9] | |
self.col = matrix.cols[index%9] | |
self.submatrix = matrix.submatrices[((index/9)/3)*3+(index%9)/3] | |
self.row.append(self) | |
self.col.append(self) | |
self.submatrix.append(self) | |
self.solutions = set(range(1,10)) | |
def solve(self): | |
if self.solved: return | |
if len(self.solutions) == 1: | |
self.setSolution(self.solutions.pop()) | |
else: | |
sol = set() | |
for cells in [self.row, self.col, self.submatrix]: | |
otherSolutions = self.cells2sols(cells, self) | |
sol |= (self.solutions - otherSolutions) | |
if len(sol) > 1: raise DeadEnd() | |
if sol: self.setSolution(sol.pop()) | |
def skim(self): | |
submatrix = set(self.submatrix) | |
for r in (set(self.row), set(self.col)): | |
subset1 = submatrix - r | |
subset2 = r - submatrix | |
solsNotIn1 = set(range(1,10)) - self.cells2sols(subset2) | |
solsNotIn2 = set(range(1,10)) - self.cells2sols(subset1) | |
for c in subset1: c.delSolutions(solsNotIn1) | |
for c in subset2: c.delSolutions(solsNotIn2) | |
def setSolution(self, val): | |
self.solved = True | |
self.solutions = set((val,)) | |
self.matrix.changed = True | |
for other in self.row+self.col+self.submatrix: | |
if other is self: continue | |
if other.solutions == self.solutions: raise DeadEnd() | |
other.delSolutions(self.solutions) | |
def delSolutions(self, val): | |
if not self.solved and val & self.solutions: | |
self.solutions -= val | |
self.matrix.changed = True | |
if not self.solutions: raise DeadEnd() | |
def __repr__(self): | |
return str(self.solved and list(self.solutions)[0] or list(self.solutions)) | |
@staticmethod | |
def cells2sols(cells, exclude=None): | |
return set(s for c in cells for s in c.solutions if c is not exclude) | |
if __name__ == "__main__": | |
input =''' | |
0,0,0,0,6,0,0,4,0 | |
0,0,0,0,0,0,0,0,9 | |
0,0,0,1,0,5,3,2,7 | |
0,0,0,0,0,1,5,0,3 | |
0,6,0,2,0,3,0,9,0 | |
1,0,8,9,0,0,0,0,0 | |
9,1,5,7,0,4,0,0,0 | |
3,0,0,0,0,0,0,0,0 | |
0,7,0,0,3,0,0,0,0 | |
''' | |
matrix = Matrix(input) | |
matrix.solve() | |
print matrix |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment