sudoku solver in Python ...

Discussion in 'Python' started by Derek Marshall, Jan 24, 2008.

  1. This is just for fun, in case someone would be interested and because
    I haven't had the pleasure of posting anything here in many years ...

    http://derek.marshall.googlepages.com/pythonsudokusolver

    Appreciate any feedback anyone who takes the time to have a look would
    want to give ...

    Yours with-too-much-time-to-kill-on-the-train'ly,
    Derek
     
    Derek Marshall, Jan 24, 2008
    #1
    1. Advertising

  2. On Jan 23, 2008, at 10:02 PM, Derek Marshall wrote:

    > This is just for fun, in case someone would be interested and because
    > I haven't had the pleasure of posting anything here in many years ...
    >
    > http://derek.marshall.googlepages.com/pythonsudokusolver
    >
    > Appreciate any feedback anyone who takes the time to have a look would
    > want to give ...
    >
    > Yours with-too-much-time-to-kill-on-the-train'ly,
    > Derek
    > --
    > http://mail.python.org/mailman/listinfo/python-list


    For those interested in this topic, here's another (much shorter) one:

    http://norvig.com/sudoku.html

    I'm not making any judgements here, though. If anyone takes the time
    to actually review them, I'd be interested in hearing any educated
    comparisons.

    Shawn
     
    Shawn Milochik, Jan 24, 2008
    #2
    1. Advertising

  3. Derek  Marshall

    Tim Roberts Guest

    Derek Marshall <> wrote:

    >This is just for fun, in case someone would be interested and because
    >I haven't had the pleasure of posting anything here in many years ...
    >
    > http://derek.marshall.googlepages.com/pythonsudokusolver
    >
    >Appreciate any feedback anyone who takes the time to have a look would
    >want to give ...


    In my view, the canonical Python sudoku solver is located here:

    http://www.ics.uci.edu/~eppstein/PADS/Sudoku.py

    This is from David Eppstein, a professor of Computer Science at the
    University of California at Irvine.

    More than just solving the puzzles, his script actually prints out the
    individual steps that lead to the solution, one by one, in readable
    English. I've used it several times just to get a hint at the next step in
    a solution. It can also create new puzzles.

    His website contains a large collection of interesting public domain Python
    scripts for numerical analysis and linear programming problems and puzzles.

    http://www.ics.uci.edu/~eppstein/
    --
    Tim Roberts,
    Providenza & Boekelheide, Inc.
     
    Tim Roberts, Jan 24, 2008
    #3
  4. Derek  Marshall

    Boris Borcic Guest

    Shawn Milochik wrote:
    > On Jan 23, 2008, at 10:02 PM, Derek Marshall wrote:
    >
    >> This is just for fun, in case someone would be interested and because
    >> I haven't had the pleasure of posting anything here in many years ...
    >>
    >> http://derek.marshall.googlepages.com/pythonsudokusolver
    >>
    >> Appreciate any feedback anyone who takes the time to have a look would
    >> want to give ...
    >>
    >> Yours with-too-much-time-to-kill-on-the-train'ly,
    >> Derek
    >> --
    >> http://mail.python.org/mailman/listinfo/python-list

    >
    > For those interested in this topic, here's another (much shorter) one:
    >
    > http://norvig.com/sudoku.html
    >
    > I'm not making any judgements here, though. If anyone takes the time
    > to actually review them, I'd be interested in hearing any educated
    > comparisons.
    >
    > Shawn


    So would I. Below is the "winner" of my hacking for an as fast as possible 110%
    pure python (no imports at all!) comprehensive sudoku solver under 50 LOCs, back
    in 2006. Performance is comparable to the solver you advertize - numbers are
    slightly better, but platform differences could easily absorb that - eg (not
    counting module initialization and not using psyco) it takes 9.3 ms average on
    the "AI escargot" problem linked to in Norwig's page, 5.6 ms/problem on some
    standard "top1465" list of hard problems, and 3.4 ms/problem on the first 1000
    on some other "top50000" list of relatively hard problems. This on my 2GHz Intel
    Centrino '05 laptop. Psyco reduces times by about 50%. Dropping performance
    requirements by half allows reducing LOC count in proportion.

    OTOH, the code although short is nearly unreadable, sorry; should probably
    feature/comment it on some web page, like the two already proposed in the
    thread. Will do if/for reviewer. Interface is calling sudoku99(problem) with
    'problem' a standard 81 character string with '0' or '.' placeholder for
    unknowns. Returns same with values filled in.

    Beware that although in practice it solved all well-formed human-solvable
    problems I could find, it is not guaranteed to deal properly (or even
    terminate?) for underdetermined problems or determined problems that would
    require exploring choicepoints with more than 2 possibilities (if such exist).

    Cheers, Boris



    w2q = [[n/9,n/81*9+n%9+243,n%81+162,n%9*9+n/243*3+n/27%3+81]
    for n in range(729)]
    q2w = (z[1] for z in sorted((x,y) for y,s in enumerate(w2q) for x in s))
    q2w = map(set,zip(*9*[q2w]))
    w2q2w = [set(w for q in qL for w in q2w[q] if w!=w0) for w0,qL in enumerate(w2q)]
    empty = set(range(729)).copy

    def sudoku99(problem) :
    givens = set(9*j+int(k)-1 for j,k in enumerate(problem) if '0'<k)
    ws=search(givens,[9]*len(q2w),empty())
    return ''.join(str(w%9+1) for w in sorted(ws))

    def search(w0s,q2nw,free) :
    while 1 :
    while w0s:
    w0 = w0s.pop()
    for q in w2q[w0] : q2nw[q]=100
    wz = w2q2w[w0]&free
    free-=wz
    for w in wz :
    for q in w2q[w] :
    n = q2nw[q] = q2nw[q]-1
    if n<2 :
    ww,=q2w[q]&free
    w0s.add(ww)
    if len(free)==81 : return free
    thres = int((len(free)+52.85)/27.5)
    ix,vmax = -1,0
    try :
    while 1 :
    ix=q2nw.index(2,ix+1)
    for w0 in (q2w[ix]&free)-w0s :
    v = len(w2q2w[w0]&free)
    if v > vmax :
    ixmax = ix
    if v >=thres : break
    vmax = v
    w0s.add(w0)
    else : continue
    break
    except : pass
    w0,w1 = q2w[ixmax]&free
    try :
    w0s.clear()
    w0s.add(w0)
    return search(w0s,q2nw[:],free.copy())
    except ValueError :
    w0s.clear()
    w0s.add(w1)
     
    Boris Borcic, Jan 24, 2008
    #4
  5. Derek  Marshall

    Thomas Thiel Guest

    On Wed, 23 Jan 2008 19:02:01 -0800 (PST), Derek Marshall wrote:

    > This is just for fun, in case someone would be interested and because
    > I haven't had the pleasure of posting anything here in many years ...
    >
    > http://derek.marshall.googlepages.com/pythonsudokusolver
    >
    > Appreciate any feedback anyone who takes the time to have a look would
    > want to give ...
    >
    > Yours with-too-much-time-to-kill-on-the-train'ly,
    > Derek



    Neither fast nor user friendly, but very concise:


    options = set([str(i) for i in range(1, 10)])

    def solve(puzzle):
    i = puzzle.find('0')
    if i < 0:
    print puzzle
    return
    exclude = set(
    puzzle[j] if i//9 == j//9 or i%9 == j%9
    or i//27 == j//27 and (i%9)//3 == (j%9)//3
    else '0'
    for j in range(81)
    )
    for option in options - exclude:
    solve(puzzle[:i] + option + puzzle[i+1:])



    solve('200375169639218457571964382152496873348752916796831245900100500800007600400089001')
    solve('054300070001620000900000315600250401003408900208061007386000009000097100070006240')
    solve('206089500900500000038060900090001003700090008100600090001050840000007001009140207')
    solve('000100005007048002020900007030002900500000004006800010800001040600280500100004000')
    solve('000897000009000001006010090030000020000574000010000060080020700500000900000763000')
    solve('500010900730200005000060070000500800800000003004007000010080000200001069006070004')
    solve('070040063002009040500000800000070300900806007008050000007000002010400700690020030')
    solve('570090180030000004080000600002405000000000000000609500005000090300000020091030075')
    solve('070040063002009040500000800000070300900806007008050000007000002010400700690020030')
    solve('180000400000800000009034500040960000520080076000053010002510700000002000007000092')
    solve('060030000045900028008000730000090050900806007080050000036000900420009380000020010')
    solve('001400000000078601000050900080000023013000560950000070005040000309180000000007300')
    solve('705020003003500000400700006000030820000000000062090000300008009000004100100070302')
    solve('001007400000020096600300000057008900930000051006900270000006005820070000005200800')
    solve('007300200300000001800620000073400005000000000500008490000067004200000006009004300')


    I can't take credit for it, though.
    It's an adaptation of a one-liner in Groovy, that comes with the
    ducumentation:

    def r(a){def i=a.indexOf(48);if(i<0)print a
    else(('1'..'9')-(0..80).collect{j->
    g={(int)it(i)==(int)it(j)};g{it/9}|g{it%9}|g{it/27}&g{it%9/3}?a[j]:'0'}).each{
    r(a[0..<i]+it+a[i+1..-1])}}

    Although this one-liner is buggy, the underlying idea is good,
    so I pilfered ;-)


    OT:
    If you're interested in a slightly more readable (and working) version:

    def r(a){
    def i = a.indexOf(48)
    if( i < 0 ){ println a; return }
    ( ('1'..'9') -
    ( 0 .. 80).collect{ j->
    i.intdiv(9) == j.intdiv(9) || i%9 == j%9 ||
    i.intdiv(27) == j.intdiv(27) && (i%9).intdiv(3) == (j%9).intdiv(3)
    ? a[j] : '0'
    }
    ).each{
    r(a[0..<i] + it + (i==80 ? "" : a[i+1..-1]))
    }
    }


    Thomas
     
    Thomas Thiel, Jan 24, 2008
    #5
  6. Derek  Marshall

    pataphor Guest

    On Thu, 24 Jan 2008 21:09:42 +0100
    Thomas Thiel <> wrote:

    > Neither fast nor user friendly, but very concise:


    This is a bit faster:

    options = set([str(i) for i in range(1, 10)])

    def allow(puzzle,i):
    exclude = set(x if i//9 == j//9 or i%9 == j%9
    or i//27 == j//27 and (i%9)//3 == (j%9)//3
    else '0' for j,x in enumerate(puzzle))
    return options-exclude

    def solve(puzzle):
    zeros = [i for i,x in enumerate(puzzle) if x == '0']
    if not zeros:
    print puzzle
    else:
    i,R = min(((j,allow(puzzle,j)) for j in zeros),
    key=lambda x: len(x[1]))
    for option in R:
    solve(puzzle[:i] + option + puzzle[i+1:])

    P.
     
    pataphor, Jan 24, 2008
    #6
  7. Derek  Marshall

    Boris Borcic Guest


    >> http://norvig.com/sudoku.html

    (...)
    > Below is the "winner" of my hacking for an as fast as
    > possible 110% pure python (no imports at all!) comprehensive sudoku
    > solver under 50 LOCs, back in 2006. Performance is comparable to the
    > solver you advertize - numbers are slightly better, but platform
    > differences could easily absorb that -


    More precise comparisons, after noting that on Norvig's pages there were
    contradictory performance numbers (obviously some 0 inserted or deleted).
    Running on my machine on the "top95" list of hard problems given on Norvig's
    page, my code takes about 7.5 ms/problem while Norvig's takes 42 ms/problem.

    So that's a 82% reduction of running time.

    Psyco.full() reduces the running time of my code to just about 4 ms/problem
    while it grows Norvig's to 47 ms/problem.

    BB

    > eg (not counting module
    > initialization and not using psyco) it takes 9.3 ms average on the "AI
    > escargot" problem linked to in Norvig's page, 5.6 ms/problem on some
    > standard "top1465" list of hard problems, and 3.4 ms/problem on the
    > first 1000 on some other "top50000" list of relatively hard problems.
    > This on my 2GHz Intel Centrino '05 laptop. Psyco reduces times by about
    > 50%. Dropping performance requirements by half allows reducing LOC count
    > in proportion.
    >
    > OTOH, the code although short is nearly unreadable, sorry; should
    > probably feature/comment it on some web page, like the two already
    > proposed in the thread. Will do if/for reviewer. Interface is calling
    > sudoku99(problem) with 'problem' a standard 81 character string with '0'
    > or '.' placeholder for unknowns. Returns same with values filled in.
    >
    > Beware that although in practice it solved all well-formed
    > human-solvable problems I could find, it is not guaranteed to deal
    > properly (or even terminate?) for underdetermined problems or determined
    > problems that would require exploring choicepoints with more than 2
    > possibilities (if such exist).
    >
    > Cheers, Boris
    >
    >
    >
    > w2q = [[n/9,n/81*9+n%9+243,n%81+162,n%9*9+n/243*3+n/27%3+81]
    > for n in range(729)]
    > q2w = (z[1] for z in sorted((x,y) for y,s in enumerate(w2q) for x in s))
    > q2w = map(set,zip(*9*[q2w]))
    > w2q2w = [set(w for q in qL for w in q2w[q] if w!=w0) for w0,qL in
    > enumerate(w2q)]
    > empty = set(range(729)).copy
    >
    > def sudoku99(problem) :
    > givens = set(9*j+int(k)-1 for j,k in enumerate(problem) if '0'<k)
    > ws=search(givens,[9]*len(q2w),empty())
    > return ''.join(str(w%9+1) for w in sorted(ws))
    >
    > def search(w0s,q2nw,free) :
    > while 1 :
    > while w0s:
    > w0 = w0s.pop()
    > for q in w2q[w0] : q2nw[q]=100
    > wz = w2q2w[w0]&free
    > free-=wz
    > for w in wz :
    > for q in w2q[w] :
    > n = q2nw[q] = q2nw[q]-1
    > if n<2 :
    > ww,=q2w[q]&free
    > w0s.add(ww)
    > if len(free)==81 : return free
    > thres = int((len(free)+52.85)/27.5)
    > ix,vmax = -1,0
    > try :
    > while 1 :
    > ix=q2nw.index(2,ix+1)
    > for w0 in (q2w[ix]&free)-w0s :
    > v = len(w2q2w[w0]&free)
    > if v > vmax :
    > ixmax = ix
    > if v >=thres : break
    > vmax = v
    > w0s.add(w0)
    > else : continue
    > break
    > except : pass
    > w0,w1 = q2w[ixmax]&free
    > try :
    > w0s.clear()
    > w0s.add(w0)
    > return search(w0s,q2nw[:],free.copy())
    > except ValueError :
    > w0s.clear()
    > w0s.add(w1)
    >
     
    Boris Borcic, Jan 25, 2008
    #7
    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. ago
    Replies:
    11
    Views:
    714
    Anton Vredegoor
    Jan 20, 2006
  2. Replies:
    0
    Views:
    329
  3. Boon

    Yet another brute force sudoku solver

    Boon, Oct 16, 2008, in forum: C Programming
    Replies:
    34
    Views:
    1,164
    user923005
    Oct 24, 2008
  4. SuDoku-X Solver

    , Aug 17, 2005, in forum: Ruby
    Replies:
    2
    Views:
    178
    Mohit Muthanna
    Aug 18, 2005
  5. Blockheads Oi Oi
    Replies:
    0
    Views:
    197
    Blockheads Oi Oi
    Jan 26, 2012
Loading...

Share This Page