sudoku dictionary attack

[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

================================================== ================
#!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()
================================================== =================

[Jonathan]

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.

[Oliver Albrecht]

Has some one an sodoku-task-generator?
Here another solutions-ways:
http://www.python-forum.de/viewtopic.php?t=3378

--
<!--Olliminatore-->input<?/>

[r.e.s.]

"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/

[Nick Atty]

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)

[Nigel Greenwood]

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