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) -- http://mail.python.org/mailman/listinfo/python-list