Brute force sudoku cracker

[my.correo.basura at gmail.com]

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