line print out for sudoku solver
Question posted by: Thekid
(Member)
on
October 1st, 2008 01:11 AM
Hi, I found this sudoku solver online and it works good but I was wondering how I could get the answer that's in matrix form, to also print out in a single comma-delimited line, instead of 9 rows of 9?
-
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 = '''5,6,7,2,3,0,0,0,1,2,0,0,0,9,1,5,6,7,8,0,1,0,0,0 ,2,0,4,0,5,0,1,2,0,7,8,9,0,2,3,0,0,0,0,5,0,0,8,9,0 ,5,6,0,2,3,0,7,0,3,4,5,0,1,2,3,0,5,9,1,2,0,7,8,9,0 ,2,6,7,8,3,4,5'''
-
matrix = Matrix(input)
-
matrix.solve()
-
print matrix
-
1
Answer Posted
Hey use the numarray or numpy to print the output in an array form
|
