sudoku solver in Python ...

[Thomas Thiel]

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