Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > sudoku solver in Python ...

Reply
Thread Tools

sudoku solver in Python ...

 
 
Derek Marshall
Guest
Posts: n/a
 
      01-24-2008
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.co...onsudokusolver

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
 
Reply With Quote
 
 
 
 
Shawn Milochik
Guest
Posts: n/a
 
      01-24-2008

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.co...onsudokusolver
>
> 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
 
Reply With Quote
 
 
 
 
Tim Roberts
Guest
Posts: n/a
 
      01-24-2008
Derek Marshall <(E-Mail Removed)> 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.co...onsudokusolver
>
>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, http://www.velocityreviews.com/forums/(E-Mail Removed)
Providenza & Boekelheide, Inc.
 
Reply With Quote
 
Boris Borcic
Guest
Posts: n/a
 
      01-24-2008
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.co...onsudokusolver
>>
>> 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)

 
Reply With Quote
 
Thomas Thiel
Guest
Posts: n/a
 
      01-24-2008
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.co...onsudokusolver
>
> 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('2003751696392184575719643821524968733487529 16796831245900100500800007600400089001')
solve('0543000700016200009000003156002504010034089 00208061007386000009000097100070006240')
solve('2060895009005000000380609000900010037000900 08100600090001050840000007001009140207')
solve('0001000050070480020209000070300029005000000 04006800010800001040600280500100004000')
solve('0008970000090000010060100900300000200005740 00010000060080020700500000900000763000')
solve('5000109007302000050000600700005008008000000 03004007000010080000200001069006070004')
solve('0700400630020090405000008000000703009008060 07008050000007000002010400700690020030')
solve('5700901800300000040800006000024050000000000 00000609500005000090300000020091030075')
solve('0700400630020090405000008000000703009008060 07008050000007000002010400700690020030')
solve('1800004000008000000090345000409600005200800 76000053010002510700000002000007000092')
solve('0600300000459000280080007300000900509008060 07080050000036000900420009380000020010')
solve('0014000000000786010000509000800000230130005 60950000070005040000309180000000007300')
solve('7050200030035000004007000060000308200000000 00062090000300008009000004100100070302')
solve('0010074000000200966003000000570089009300000 51006900270000006005820070000005200800')
solve('0073002003000000018006200000734000050000000 00500008490000067004200000006009004300')


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(4;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(4
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
 
Reply With Quote
 
pataphor
Guest
Posts: n/a
 
      01-24-2008
On Thu, 24 Jan 2008 21:09:42 +0100
Thomas Thiel <(E-Mail Removed)> 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.

 
Reply With Quote
 
Boris Borcic
Guest
Posts: n/a
 
      01-25-2008

>> 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)
>

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
constraint based killer sudoku solver performance improvements Blockheads Oi Oi Python 0 01-26-2012 06:21 PM
Yet another brute force sudoku solver Boon C Programming 34 10-24-2008 12:39 AM
Sudoku solver: reduction + brute force ago Python 11 01-20-2006 11:55 AM
A learning exercise...yet another Sudoku solver with GUI engsolnorm@hotmail.com Python 0 01-19-2006 02:04 AM
SuDoku-X Solver astrodean@yahoo.co.uk Ruby 2 08-18-2005 02:07 AM



Advertisments