I did some work recently to enumerate sudoku solutions. Here's my idea of how to do it which seems to contradict an awful lot of the messages in this thread. Just wondered if anyone here could briefly explain what bad assumptions I've made please?
Thanks, sub1ime_uk
------------------------------------------------------------------------------------
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
==================================================================
- Code: Select all
#!python
#
# sudoku.py - generate all valid sudoku solutions
#
# Usage: sudoku <N> <S>
# 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()
===================================================================
