Sudoku solver: reduction + brute force

[Carl Cerecke]

ago wrote:
>> But to inflate my ego beyond the known universe, here is my solver
>>(that solves the avove mentioned grid reasonably fast). I suppose the
>>only difference is that is uses 3, rather than 2, rules to simplify
>>before starting tree-like search.
> 
> 
> Thanks for the nice problem and the nice post.

While we're on the topic of sudoku solvers we've written...

I have a simple brute-force only (DFS) solver that is reasonably fast 
considering the algorithm used. It also will find and print all 
solutions, and give an estimate of the difficulty of a board. The 
estimate is simply the number of nodes in the search tree. I'm guessing 
that the number is an approximate measure of the difficulty a human 
would have of solving the problem; I've never actually solved one of 
these by hand.... Once I'd written the program I sort-of lost interest.

The first three sample boards included are all quite difficult, and take 
some time to solve (and verify no other solutions exist!) with a 
depth-first search. Your reduction-first approach makes short work of 
them, though. On the other hand, my version probably didn't take as long 
to write!

Here it is:
#!/usr/bin/env python
# Copyright 2005 Carl Cerecke
# Permission is granted to use, copy, modify, and distribute the code 
and/or derived works of the code.
#import psyco
#psyco.full()

import copy

def compute_edge_cells():
     global edge_ls
     edge_ls = []
     for x in range(9):
         for y in range(9):
             ls = []
             for i in range(9):
                 if i != x:
                     ls.append((i,y))
                 if i != y:
                     ls.append((x,i))
             xblock = x/3
             yblock = y/3
             for bx in range(3):
                 for by in range(3):
                     rx = xblock*3+bx
                     ry = yblock*3+by
                     if rx != x and ry != y:
                         ls.append((rx,ry))
             edge_ls.append(tuple(ls))


class Board(object):

     board_count = 0
     solutions = 0

     def __init__(self, board, empties = None, init=1):
         self.board = board
         self.empties = empties
         Board.board_count += 1
         if init:
             self.empties = []
             for x in range(9):
                 for y in range(9):
                     if self.board[y][x] == 0:
                         self.empties.append((x,y))
                     else:
                         if self.board[y][x] not in self.valids(x,y):
                             print "bad board",x,y


     def valids(self,x,y):
         ls = [0,1,2,3,4,5,6,7,8,9]
         for ex,ey in edge_ls[x*9+y]:
             ls[self.board[ey][ex]] = 0
         #return [x for x in ls if x != 0]
         return filter(None, ls)

     def __repr__(self):
         return '\n'.join([''.join(`x`) for x in self.board])

     def solve(self):
         if self.empties == []:
             print "found solution:"
             print self
             Board.solutions += 1
             return
         x,y = self.empties[0]
         for n in self.valids(x,y):
             new_board = list(self.board)
             new_board[y] = list(new_board[y])
             new_board[y][x] = n
             new_board[y] = tuple(new_board[y])
             new_board = tuple(new_board)
             board = Board(new_board, self.empties[1:], 0)
             board.solve()


compute_edge_cells()
def solve(b):
     Board.solutions = 0
     Board.board_count = 0
     b.solve()
     print b.board_count
     print "solutions:",b.solutions

a = Board((
     (0,0,0,1,0,9,0,2,0),
     (0,0,8,0,0,5,6,0,0),
     (2,0,0,0,0,0,0,0,1),
     (0,0,0,4,0,7,0,0,6),
     (0,0,6,0,0,0,3,0,0),
     (7,0,0,9,0,1,0,0,0),
     (5,0,0,0,0,0,0,0,2),
     (0,0,7,2,0,0,9,0,0),
     (0,4,0,5,0,8,0,7,0)))
b = Board((
(0, 2, 0, 0, 0, 0, 0, 0, 0),
(0, 0, 0, 6, 0, 0, 0, 0, 3),
(0, 7, 4, 0, 8, 0, 0, 0, 0),
(0, 0, 0, 0, 0, 3, 0, 0, 2),
(0, 8, 0, 0, 4, 0, 0, 1, 0),
(6, 0, 0, 5, 0, 0, 0, 0, 0),
(0, 0, 0, 0, 1, 0, 7, 8, 0),
(5, 0, 0, 0, 0, 9, 0, 0, 0),
(0, 0, 0, 0, 0, 0, 0, 4, 0)))

c = Board((
(0, 0, 0, 0, 0, 9, 0, 0, 0),
(0, 0, 0, 0, 1, 4, 7, 0, 0),
(0, 0, 2, 0, 0, 0, 0, 0, 0),
(7, 0, 0, 0, 0, 0, 0, 8, 6),
(5, 0, 0, 0, 3, 0, 0, 0, 2),
(9, 4, 0, 0, 0, 0, 0, 0, 1),
(0, 0, 0, 0, 0, 0, 4, 0, 0),
(0, 0, 6, 2, 5, 0, 0, 0, 0),
(0, 0, 0, 8, 0, 0, 0, 0, 0)))

d = Board((
(0,0,0,0,9,6,8,0,0),
(0,0,1,0,0,0,0,7,0),
(0,2,0,0,0,0,0,0,3),
(0,3,0,0,0,8,0,0,6),
(0,0,4,0,2,0,3,0,0),
(6,0,0,5,0,0,0,8,0),
(9,0,0,0,0,0,0,5,0),
(0,7,0,0,0,0,1,0,0),
(0,0,5,9,4,0,0,0,0)))

solve(a)
solve(b)
solve(c)
solve(d)