Sudoku solver: reduction + brute force
Carl Cerecke
cdc at maxnet.co.nz
Wed Jan 18 16:06:21 EST 2006
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)
More information about the Python-list
mailing list