in [Python]

Prev: Python 2.4 decompiler
Next: triangulation
From: Anton Vredegoor on 18 Sep 2005 08:41 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()
From: Gregory Bond on 19 Sep 2005 01:59 My current solver does 1 level of backtracking (i.e. constant space, and bounded time) only, and it has been able to solve every puzzle I've thrown at it. It's based on the usual logic and book-keeping for the most part. (It also explains how it comes up with each answer step as it goes, which is handy...) Once it gets to the stage where it needs to guess, it arranges all the unknowns then tries them in some arbitary order. It saves the state, applies the guess (square x,y is N) and then re-applies all the logic rules. There are 3 possible outcomes from here: - We've solved it, which is good (this happens surprisingly often....) - We can't solve it using this guess (so ignore this possibility, restore the state & try the next guess) - The Resulting puzzle is badly formed / inconsistant (represented by a python exception, naturally!) In this case, we know the guessed square/number is not valid, so we backtrack (restore the state before we made this guess), remove that possibility (x,y is N) and then apply all the logic rules again. Often times, this is enough to solve, but it usually progreses things a little even if it doesn't solve it. I've not yet found a (9x9) puzzle that this cannot solve. The downside is that it cannot detect cases where there are multiple solutions.
From: Antoon Pardon on 19 Sep 2005 03:12 Op 2005-09-16, my.correo.basura (a)gmail.com schreef <my.correo.basura(a)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. I don't think so. I regularly solve one and I never needed to try something out, to see if it worked or not except when there were muliple solutions. I think it is a beautifull problem, to make people think of how they could code some of their thought processes, which would be a more fruitfull experience as programming this with backtracking. -- Antoon Pardon
From: Antoon Pardon on 19 Sep 2005 03:17 Op 2005-09-17, Tom Anderson schreef <twic (a)urchin.earth.li>:> On Fri, 16 Sep 2005, Bas wrote: > >> -any ideas how to easily incorporate advanced solving strategies? >> solve(problem1) and solve(problem2) give solutions, but solve(problem3) >> gets stuck... > > the only way to solve arbitrary sudoku problems is to guess. That is strange, in al the puzzles that I have solved untill now, I never needed to guess, unless the puzzle had multiple solutions, which personnally I find inferior. -- Antoon Pardon
From: Gerard Flanagan on 19 Sep 2005 03:49
Anton Vredegoor wrote: > I like to program sudoku and review such > code. Some non-Python examples: APL (The Horror! The Horror!...): http://www.vector.org.uk/archive/v214/sudoku.htm and my own effort with Excel/C# (very humble - needs work): http://exmachinis.net/code/cs/2005/08/4.html |