Brute force sudoku cracker
in [Python]
|
Prev: Python 2.4 decompiler
Next: triangulation
From: Bas on 16 Sep 2005 16:45 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. -any ideas how to easily incorporate advanced solving strategies? solve(problem1) and solve(problem2) give solutions, but solve(problem3) gets stuck... -any improvements possible for the current code? I didn't play a lot with python yet, so I probably missed some typical python tricks, like converting for-loops to list expressions. TIA, Bas *********** from itertools import ifilterfalse problem1 = [' 63 7 ', ' 69 8', '9 7 2', ' 2 1 8 ', ' 5 8 6 9 ', ' 9 7 2 ', '6 1 3', '7 45 ', ' 9 14 '] problem2 = [' 3 9 7', ' 1 8 ', ' 1 9 ', ' 49 5 6', ' 2 1 ', '5 6 74 ', ' 5 1 ', ' 4 2 ', '7 5 3 '] problem3 = [' 3 5 81 ', ' 76 9 ', '4 ', ' 439 5 6', ' 1 7 ', '6 8 193 ', ' 9', ' 9 86 ', ' 61 2 8 '] #define horizontal lines, vertical lines and 3x3 blocks groups = [range(9*i,9*i+9) for i in range(9)] + \ [range(i,81,9) for i in range(9)] + \ [range(0+27*i+3*j,3+27*i+3*j) + range(9+27*i+3*j,12+27*i+3*j) + \ range(18+27*i+3*j,21+27*i+3*j) for i in range(3) for j in range(3)] def display(fields): for i in range(9): line = '' for j in range(9): if len(fields[9*i+j]) == 1: line += ' ' + str(fields[9*i+j][0]) else: line += ' ' print line def all(seq, pred=bool): "Returns True if pred(x) is True for every element in the iterable" for elem in ifilterfalse(pred, seq): return False return True def product(seq): prod = 1 for item in seq: prod *= item return prod def solve(problem): fields = [range(1,10) for i in range(81)] #fill with all posibilities for all fields for i,line in enumerate(problem): for j,letter in enumerate(line): if letter != ' ': fields[9*i+j]=[int(letter)] #seed with numbers from problem oldpos = 0 while True: pos = product(len(field) for field in fields) if pos == oldpos: #no new possibilities eliminated, so stop break display(fields) print pos,'possibilities' oldpos = pos for group in groups: for index in group: field = fields[index] if len(field) == 1: #if only number possible for field remove it from other fields in group for ind in group: if ind != index: try: fields[ind].remove(field[0]) except ValueError: pass else: #check if field contains number that does not exist in rest of group for f in field: if all(f not in fields[ind] \ for ind in group if ind!=index): fields[index] = [f] break
From: my.correo.basura on 16 Sep 2005 18:17 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. The cost is still exponential but it works nicely with small problems. Fortunately, a 9x9 grid is small enough. I programmed this about two months ago, it's not really pretty but it works perfectly. Beware, some variable names are in spansih... [let's hope the tabs are kept...] Regards, Al from sets import Set class sudoku: def __init__(self,cadena): self.numeros=Set(range(1, 10)) self.m=[['X']*9 for i in range(9)] for fila in range(9): for columna in range(9): if cadena[fila*9 + columna].isdigit(): self.m[fila][columna]=int(cadena[fila*9+columna]) self.posiciones=[(i,j) for i in range(9) for j in range(9) if self.m[i][j]=='X'] def __repr__(self): res="" for fila in range(9): if fila%3==0: res+= "-------------------------\n" for columna in range(9): if columna%3==0: res+= "| " res+="%s "%str(self.m[fila][columna]) res+= "|\n" res+= "-------------------------\n" return res def fila(self,fila, columna): return self.numeros-Set(elem for elem in self.m[fila] if elem!='X') def columna(self,fila, columna): return self.numeros-Set(self.m[i][columna] for i in range(9) if self.m[i][columna]!='X') def cuadro(self,fila, columna): s=Set() f_ini=3*(fila/3) c_ini=3*(columna/3) for f in range(f_ini, f_ini+3): for c in range(c_ini, c_ini+3): if self.m[f][c]!='X' and self.m[f][c] not in s: s.add(self.m[f][c]) return self.numeros-s def resuelve(self): print "Resolviendo" def actua(i): if i==len(self.posiciones): print self return f, c=self.posiciones[i] posibles=self.fila(f, c).intersection(self.columna(f, c)).intersection(self.cuadro(f, c)) for num in posibles: self.m[f][c]=num actua(i+1) self.m[f][c]='X' actua(0) def main(): problem3=" 3 5 81 76 9 4 439 5 6 1 7 6 8 193 9 9 86 61 2 8 " t=sudoku(problem3) print t t.resuelve() if __name__=="__main__": main()
From: Sybren Stuvel on 17 Sep 2005 05:39 Bas enlightened us with: > 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. I've got a solver too - I'm joining the Linux Format programming contest. My program can solve and create Sudoku puzzles - and not only 9x9 ones. Check http://www.unrealtower.org/sodoku. In the LFX programming contest they call the puzzle Sodoku, not Sudoku, so that's why I'm sticking with the name Sodoku for now. > -any improvements possible for the current code? I didn't play a lot > with python yet, so I probably missed some typical python tricks, > like converting for-loops to list expressions. It all depends on what you want to do. My program can create & solve puzzles from any size, load and save them to disk, check them for validity and rank them ('easy', 'medium', 'hard', 'near impossible'). It also implements a puzzle in a class, so it can be used in an OOP fashion. > def all(seq, pred=bool): What's this? What is bool? Sybren -- The problem with the world is stupidity. Not saying there should be a capital punishment for stupidity, but why don't we just take the safety labels off of everything and let the problem solve itself? Frank Zappa
From: Tom Anderson on 17 Sep 2005 07:34 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. of course, you have to deal with guessing wrongly, and it helps if you can make good guesses! i wrote a solver based entirely on guessing and backtracking a few months ago; it's fairly simple, although i wrote it in fairly fine-grained java, so there's actually quite a lot of code. i had a very different program structure to you, since i was only doing guesswork; i had a recursive function that looked like this: def solve(grid): """Solves a grid. The solution is written in the grid; if no solution can be found, does nothing to the grid. Returns True if a solution was found, False if not. """ x, y = pick_an_empty_cell_to_try(grid) letters = letters_which_can_be_written_in_this_cell(grid, x, y) if (letters == []): return False # there are no legal moves; give up for letter in letters: grid.write(x, y, letter) # try a move ... if (solve(grid)): return True # we win! grid.erase(x, y) # ... undo it if it didn't work return False # none of the legal moves work; give up the implementation of the grid class is pretty straightforward - it's just a two-dimensional matrix with some bells and whistles. letters_which_can_be_written_in_this_cell is also fairly simple, although it can be made a lot faster by keeping summary information in the grid object: i had a set for each row, column and region saying which letters had been written already, so the set of available letters was the inverse of the union of the sets relevant to the cell; the sets were implemented as bitmaps, so this was all very fast. the only tricky bit is pick_an_empty_cell_to_try; you can have fun trying different heuristics here! the nice thing is that it's okay to use quite computationally expensive heuristics, since a modestly better choice can save huge numbers of recursions. there are a number of much, much more advanced algorithms out there, doing all sorts of clever stuff. however, my algorithm solves any sudoku i can throw at it (barring seriously unreasonable stuff) in under a second, so i'm happy with it. tom -- I content myself with the Speculative part [...], I care not for the Practick. I seldom bring any thing to use, 'tis not my way. Knowledge is my ultimate end. -- Sir Nicholas Gimcrack
From: Pierre Barbier de Reuille on 17 Sep 2005 09:29
Tom Anderson a ýcrit : > 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. Well, that's true, but most of the sudoku puzzles can be solved in linear time ! And also having a linear time solving algorithm allows you to really reduce the time used when you need backtracking. BTW, the three given examples can be solved without backtracking. I made one very recently (mmhh ... first complete version made yesterday, still need a little bit of debug on the backtracking part), and it's pretty quick (made in Ruby but well, I suppose timing are similar), it never get stuck for long even if it fails, it fails quickly ... Pierre |