Bas ha escrito:
> Hi group,
>
> I came across some of these online sudoku games and thought after
> playing a game or two that I'd better waste my time writing a solver
> than play the game itself any longer. I managed to write a pretty dumb
> brute force solver that can at least solve the easy cases pretty fast.
>
> It basically works by listing all 9 possible numbers for all 81 fields
> and keeps on striking out possibilities until it is done.
> [snip]
This problem is desperately begging for backtracking. The cost is still
exponential but it works nicely with small problems. Fortunately, a 9x9
grid is small enough. I programmed this about two months ago, it's not
really pretty but it works perfectly. Beware, some variable names are
in spansih...
[let's hope the tabs are kept...]
Regards,
Al
from sets import Set
class sudoku:
def __init__(self,cadena):
self.numeros=Set(range(1, 10))
self.m=[['X']*9 for i in range(9)]
for fila in range(9):
for columna in range(9):
if cadena[fila*9 + columna].isdigit():
self.m[fila][columna]=int(cadena[fila*9+columna])
self.posiciones=[(i,j) for i in range(9) for j in range(9) if
self.m[i][j]=='X']
def __repr__(self):
res=""
for fila in range(9):
if fila%3==0: res+= "-------------------------\n"
for columna in range(9):
if columna%3==0: res+= "| "
res+="%s "%str(self.m[fila][columna])
res+= "|\n"
res+= "-------------------------\n"
return res
def fila(self,fila, columna):
return self.numeros-Set(elem for elem in self.m[fila] if
elem!='X')
def columna(self,fila, columna):
return self.numeros-Set(self.m[i][columna] for i in range(9)
if self.m[i][columna]!='X')
def cuadro(self,fila, columna):
s=Set()
f_ini=3*(fila/3)
c_ini=3*(columna/3)
for f in range(f_ini, f_ini+3):
for c in range(c_ini, c_ini+3):
if self.m[f][c]!='X' and self.m[f][c] not in s:
s.add(self.m[f][c])
return self.numeros-s
def resuelve(self):
print "Resolviendo"
def actua(i):
if i==len(self.posiciones):
print self
return
f, c=self.posiciones[i]
posibles=self.fila(f, c).intersection(self.columna(f,
c)).intersection(self.cuadro(f, c))
for num in posibles:
self.m[f][c]=num
actua(i+1)
self.m[f][c]='X'
actua(0)
def main():
problem3=" 3 5 81 76 9 4 439 5 6 1 7 6 8 193
9 9 86 61 2 8 "
t=sudoku(problem3)
print t
t.resuelve()
if __name__=="__main__":
main()
--
http://mail.python.org/mailman/listinfo/python-list
