Brute force sudoku cracker

my.correo.basura at gmail.com my.correo.basura at gmail.com
Sat Sep 17 00:17:58 CEST 2005

```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:
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):
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')

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:

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,
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()

```