Brute force sudoku cracker

[Anton Vredegoor]

Diez B. Roggisch wrote:
> As everyone posts his, I'll do the same :) It uses some constraint based
> solving techniques - but not too complicated ones. When stuck, it
> backtracks. So far it never failed me, but I haven't tested it too
> thouroughly.

Thanks to all for sharing. I like to program sudoku and review such
code. So below here is my current file, I think it uses some techniques
not yet posted here. It also has a difficult 16x16 puzzle which I know
to be solvable (barring typing mistakes) but which my file can't solve
before I get tired of waiting, this might draw some heavyweights in the
ring :-)

I have also read the sudoku wiki page:

http://en.wikipedia.org/wiki/Sudoku

which was very helpfull and interesting (especially the link to Knuths
paper about dancing links was nice, even though I think (but maybe
wrongly so) that we don't need dancing links now that we've got sets,
but it's still a very very interesting paper)

I think the first important step is to realize that some variations
have fewer values so that it is possible to reduce the search space
early. Currently I'm exploring ideas about contigengies as explained in
the wiki above which seems promising, but I haven't found a nice way to
implement them yet. Maybe an easy optimization would be to find values
that don't come up often and choose variations containing those. And
maybe I should switch to an approach that has possibility values inside
the cells instead of computing them on the fly each time, that could
make contigency elimination easier.

Anton


from __future__ import generators
from sets import Set as set

problem1 = ['063000700','000690008','900007002',
            '002010080','050806090','090070200',
            '600100003','700045000','009000140']

problem2 = ['030009007','010080000','000100090',
            '004905006','020000010','500607400',
            '050001000','000040020','700500030']

problem3 = ['030500810','000760090','400000000',
            '043905006','010000070','600801930',
            '000000009','090086000','061002080']

problem4 = ['004530080','060009000','900000005',
            '000800350','000000000','027006000',
            '800000007','000300040','090072600']

X =[' 1  0  0  0  0 12  0 10 11  7  6  0  0  4  0  0',
    ' 0  7  0  0 15 13  0  0  0  0  2  0  0  8  0  0',
    ' 3  0  0  0  4  0  0  0  0  5  0 12  0 16  0  0',
    ' 0  0 14  2  0  9  0  0  0  0  1  0  0  0  0  0',
    '10 15  0  1  0  0  0  2  0 16  0  0  3  0  0  0',
    '12  0  0  3  0  0 15  0  0 13  0  4  0  1  9  5',
    ' 5  0 11  0  7  0  8  0  0  0  0  0  0 15  0  0',
    ' 7 13  0 16  0  0  0  6  0  0  0 14  0 10  0  0',
    ' 0  0 13  0 11  0  0  0 10  0  0  0  1  0 12  0',
    ' 0  0  7  0  0  0  0  0  0  3  0 16  0 14  0 13',
    '16  8  0  0 14  0  5  0  0 15  0  0  4  0  0  6',
    ' 0  0  0  9  0  0  4  0  1  0  0  0  2  0  0  7',
    ' 0  0  0  0  0 16  0  0  0  0  8  0 10  5  0  0',
    ' 0  0  4  0 12  0  6  0  0  0 16  7  0  0  0 14',
    ' 0  0  6  0  0  1  0  0  0  0 12 13  0  0 11  0',
    ' 0  0 15  0  0  8 11  3  2  0  9  0  0  0  0  1']

problem5 = [row.split() for row in X]

class State:

    def __init__(self,solved,unsolved):
        self.solved = solved
        self.unsolved = unsolved
        self.size = int((len(solved)+len(unsolved))**.25)

    def choiceset(self,x,y):
        "the set of possible choices for an empty cell"
        sz = self.size
        res = set(range(1,sz*sz+1))
        r,c = x/sz*sz,y/sz*sz
        for (i,j),v in self.solved.iteritems():
            if x == i or y == j or (r<=i<r+sz and c<=j<c+sz):
                 res.discard(v)
        return res

    def celldict(self):
        """dictionary of (cellcoords,choiceset) for each empty cell
           if *any* empty cell cannot be filled return an empty dict
           to signal an illegal position
        """
        res = {}
        for x,y in self.unsolved:
                c = self.choiceset(x,y)
                if not c:
                    return {}
                res[x,y] = c
        return res

class Node:

    def __init__(self,state):
        self.state = state
        self.issolved = not bool(state.unsolved)

    def children(self):
        state = self.state
        cd = state.celldict()
        if cd: #position is still legal
            ml = min([len(x) for x in cd.itervalues()])
            #select  empty cells which have  the minimum number of
choices
            items = [(k,v) for k,v in cd.iteritems() if len(v) == ml]
            (x,y),S = min(items) #arbitrary choice of cell here
            for v in S:
                solved,unsolved =
dict(state.solved),dict(state.unsolved)
                solved[x,y] = v
                del unsolved[x,y]
                yield Node(State(solved,unsolved))

    def __repr__(self):
        R = range(self.state.size**2)
        res = [["__" for i in R] for j in R]+['']
        for (i,j),v in self.state.solved.iteritems():
            res[i][j] = "%02i" %v
        return '\n'.join(map(' '.join,res))

def solutions(N):
    if N.issolved:
        yield N
    else:
        for child in N.children():
            for g in solutions(child):
                yield g

def todicts(P):
    M = [map(int,row) for row in P]
    solved = {}
    unsolved = {}
    for i,row in enumerate(M):
        for j,x in enumerate(row):
            if x:
                solved[i,j] = x
            else:
                unsolved[i,j] = x
    return solved,unsolved

def test():
    solved,unsolved = todicts(problem4)
    N = Node(State(solved,unsolved))
    print N
    for S in solutions(N):
        print S
        
if __name__=='__main__':
    test()