443,404 Members | 1,074 Online
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,404 IT Pros & Developers. It's quick & easy.

# sudoku dictionary attack

 P: n/a Thought I'd offer a method for solving all possible 9x9 sudoku puzzles in one go. It'll takes a bit of time to run however (and 9x9 seems to be about as big as is reasonably possible before combinatorial explosion completely scuppers this type of program)... Basic idea:- Start with a grid initialised with: 123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678 Note that all rows and columns contain all 9 digits (but that the sub-tiles aren't correct for a sudoku solution). Next write a program which permutes all 9 columns, and then for each of those permutations permutes the last 8 rows. This will, I believe, generate all possible grids with no digit repetitions in any row or column. It will generate 14,631,321,600 (9!*8!) possible sudoku candidates. Finally, check each candidate to see if any 3x3 subtile has a repeated digit in it and discard as soon as a repeat is found (sooner the better). Any that come through unscathed get written as a 82 (81 + lf) char string to an output file. I've written a short program (in Python; see below) that tries out this idea. Indications are that my HP nc6000 laptop can check around 30,000 candidates/sec and that c.0.15% of them are valid sudoku solutions. That means it would take around 6.5 days to generate the between 20-30 million possible sudoku solutions it will find. That would require around 2GB in uncompressed disk storage. Gzip does a VERY good job of compressing files containing this type of data -- so I'd expect well over 80% compression (might even fit on a CD then). Once you've generated the solution data then comes the fun of searching it efficiently which I leave as an exercise for the reader :-) Regards, sub1ime_uk (at) yahoo (dot) com ================================================== ================ #!python # # sudoku.py - generate all valid sudoku solutions # # Usage: sudoku # eg: sudoku 9 3 # Whare:- # N is the grid size (ie 9 for 9x9) # S is the sub-tile size (3 for 3x3) # # (c) 2005 sub1ime_uk (at) yahoo (dot) com # import sys from gzip import GzipFile from time import time def permute(s): if len(s)==0: return if len(s)==1: yield s return for i in range(len(s)): for t in permute(s[:i]+s[i+1:]): yield s[i:i+1]+t return def populate(sz, ini): tile = [] for i in range(sz): tile.append([]) for j in range(sz): x = chr((i+j)%sz+ord(ini)) tile[i].append(x) return tile def subtilesok(t, c, r, n, s): for x in range(0, n, s): for y in range(0, n, s): d = {} for i in range(s): cn = c[x+i] for j in range(s): rn = r[y+j] d[t[cn][rn]] = 1 if len(d.keys())!=n: return 0 return 1 def displaytile(t, c, r, lf): lfstr='' print for i in r: row = [] for j in c: row.append(t[j][i]) r=''.join(row) lfstr += r print " ",r print lf.write(lfstr+"\n") def fact(n): if n<2: return 1 return n*fact(n-1) if __name__ == '__main__': st = time() logf = GzipFile("c:\\temp\\sudoku.gz", "w") N=int(sys.argv[1]) S=int(sys.argv[2]) estimate = fact(N)*fact(N-1) if N!=S*S: print "Subtile size", S, "not sqrt of tile size", N sys.exit(1) cols = [x for x in range(N)] rows = [x for x in range(1, N)] primarytile = populate(N, '1') count = 0 answc = 0 for colp in permute(cols): for rowp in permute(rows): count += 1 if subtilesok(primarytile, colp, [0]+rowp, N, S): answc += 1 ct = time() et=ct-st if et>0.0: print "Found: %d out of %d (%.2f%%) checked" % (answc, count, (answc*100./count)) print "Progress: %.2f%%" % ((count*100./estimate)) print "Elapsed time: %.2f secs, checked: %d/s, found %d/s." % (et, (count/et), (answc/et)) print "Estimate time to go: %.2f hours" % ((estimate-count)*et/(count*3600.)) else: print "%d / %d (%5.2f%%)" % (answc, count, (answc*100./count)) displaytile(primarytile, colp, [0]+rowp, logf) print print "Checked", count,"tiles. Found", answc,"answers." logf.close() sys.exit() ================================================== ================= Jul 19 '05 #1
5 Replies

 P: n/a su********@yahoo.com wrote: Thought I'd offer a method for solving all possible 9x9 sudoku puzzles in one go. It'll takes a bit of time to run however (and 9x9 seems to be about as big as is reasonably possible before combinatorial explosion completely scuppers this type of program)... Basic idea:- Start with a grid initialised with: 123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678 Note that all rows and columns contain all 9 digits (but that the sub-tiles aren't correct for a sudoku solution). Next write a program which permutes all 9 columns, and then for each of those permutations permutes the last 8 rows. This will, I believe, generate all possible grids with no digit repetitions in any row or column. It will generate 14,631,321,600 (9!*8!) possible sudoku candidates. Finally, check each candidate to see if any 3x3 subtile has a repeated digit in it and discard as soon as a repeat is found (sooner the better). Any that come through unscathed get written as a 82 (81 + lf) char string to an output file. I'm having trouble coming up with anything that fits this grid: ...12..... ...2x..... .......... .......... .......... .......... .......... .......... .......... where x is not 3, by permuting columns, then rows. You may also have to permute the numbers. Although, even then, x=1 is still impossible. Jul 19 '05 #2

 P: n/a Has some one an sodoku-task-generator? Here another solutions-ways: http://www.python-forum.de/viewtopic.php?t=3378 -- input Jul 19 '05 #3

 P: n/a "Oliver Albrecht" <55*********@t-online.de> wrote ... Has some one an sodoku-task-generator? Sudoku puzzles can be generated (and solved) online at http://act365.com/sudoku/ Jul 19 '05 #4

 P: n/a On Mon, 20 Jun 2005 23:30:27 +0200, Oliver Albrecht <55*********@t-online.de> wrote: Has some one an sodoku-task-generator?Here another solutions-ways:http://www.python-forum.de/viewtopic.php?t=3378 It's presumably easy to turn a solver into a generator. Start with a random grid, and remove squares at random, and then solve it. Once solving it reaches a certain level of difficulty, then there's your problem. -- On-line canal route planner: http://www.canalplan.org.uk (Waterways World site of the month, April 2001) Jul 19 '05 #5

 P: n/a Nick Atty wrote: On-line canal route planner: http://www.canalplan.org.uk So the Travelling Salesman goes by narrow boat these days, does he? Nigel -- ScriptMaster language resources (Chinese/Modern & Classical Greek/IPA/Persian/Russian/Turkish): http://www.elgin.free-online.co.uk Jul 19 '05 #6

### This discussion thread is closed

Replies have been disabled for this discussion.