sudoku dictionary attack

Discussion in 'Python' started by sub1ime_uk@yahoo.com, Jun 20, 2005.

  1. Guest

    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.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])
    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()
    ===================================================================
    , Jun 20, 2005
    #1
    1. Advertising

  2. Jonathan Guest

    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.
    Jonathan, Jun 20, 2005
    #2
    1. Advertising

  3. Oliver Albrecht, Jun 20, 2005
    #3
  4. r.e.s. Guest

    "Oliver Albrecht" <> wrote ...
    > Has some one an sodoku-task-generator?


    Sudoku puzzles can be generated (and solved) online at
    http://act365.com/sudoku/
    r.e.s., Jun 21, 2005
    #4
  5. Nick Atty Guest

    On Mon, 20 Jun 2005 23:30:27 +0200, Oliver Albrecht
    <> 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)
    Nick Atty, Jun 21, 2005
    #5
  6. Nigel Greenwood, Jun 22, 2005
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    3
    Views:
    1,014
    Oliver Wong
    Apr 26, 2006
  2. dorayme

    The Guardian's website Sudoku

    dorayme, May 31, 2006, in forum: HTML
    Replies:
    12
    Views:
    835
    Jim Higson
    Jun 4, 2006
  3. Bas

    Brute force sudoku cracker

    Bas, Sep 16, 2005, in forum: Python
    Replies:
    21
    Views:
    3,197
    Dennis Lee Bieber
    Sep 23, 2005
  4. ago
    Replies:
    11
    Views:
    681
    Anton Vredegoor
    Jan 20, 2006
  5. Replies:
    0
    Views:
    304
Loading...

Share This Page