Smart Sudoku Golf

Question

Hello all,

The point of this question is to create the shortest not abusively slow Sudoku solver. This is defined as: don't recurse when there are spots on the board which can only possibly be one digit.

Here is the shortest I have so far in python:

r=range(81)
s=range(1,10)
def R(A):
    bzt={}
    for i in r:
        if A[i]!=0: continue; 
        h={}
        for j in r:
            h[A[j]if(j/9==i/9 or j%9==i%9 or(j/27==i/27)and((j%9/3)==(i%9/3)))else 0]=1
        bzt[9-len(h)]=h,i
    for l,(h,i)in sorted(bzt.items(),key=lambda x:x[0]):
        for j in s:
            if j not in h:
                A[i]=j
                if R(A):return 1
        A[i]=0;return 0
    print A;return 1

R(map(int, "080007095010020000309581000500000300400000006006000007000762409000050020820400060"))

The last line I take to be part of the cmd line input, it can be changed to:

import sys; R(map(int, sys.argv[1]);

This is similar to other sudoku golf challenges, except that I want to eliminate unnecessary recursion. Any language is acceptable. The challenge is on!

Answer 1

I've just trimmed the python a bit here:

r=range(81);s=range(1,10)
def R(A):
    z={}
    for i in r:
        if A[i]!=0:continue
        h={}
        for j in r:h[A[j]if j/9==i/9 or j%9==i%9 or j/27==i/27 and j%9/3==i%9/3 else 0]=1
        z[9-len(h)]=h,i
    for l,(h,i)in sorted(z.items(),cmp,lambda x:x[0]):
        for j in s:
            if j not in h:
                A[i]=j
                if R(A):return A
        A[i]=0;return[]
    return A

print R(map(int, "080007095010020000309581000500000300400000006006000007000762409000050020820400060"))

This is a hefty 410 characters, 250 if you don't count whitespace. If you just turn it into perl you'll undoubtedly be better than mine!

Answer 2

I haven't really made much of a change - the algorithm is identical, but here are a few further micro-optimisations you can make to your python code.

• No need for !=0, 0 is false in a boolean context.

• a if c else b is more expensive than using [a,b][c] if you don't need short-circuiting, hence you can use h[ [0,A[j]][j/9.. rest of boolean condition]. Even better is to exploit the fact that you want 0 in the false case, and so multiply by the boolean value (treated as either 0*A[j] (ie. 0) or 1*A[j] (ie. A[j]).

• You can omit spaces between digits and identifiers. eg "9 or" -> "9or"

• You can omit the key to sorted(). Since you're sorting on the first element, a normal sort will produce effectively the same order (unless you're relying on stability, which it doesn't look like)

• You can save a couple of bytes by omitting the .items() call, and just assign h,i in the next line to z[l]

• You only use s once - no point in using a variable. You can also avoid using range() by selecting the appropriate slice of r instead (r[1:10])

• j not in h can become (j in h)-1 (relying on True == 1 in integer context)

• [Edit] You can also replace the first for loop's construction of h with a dict constructor and a generator expression. This lets you compress the logic onto one line, saving 10 bytes in total.

More generally, you probably want to think about ways to change the algorithm to reduce the levels of nesting. Every level gives an additional byte per line within in python, which accumulates.

Here's what I've got so far (I've switched to 1 space per indent so that you can get an accurate picture of required characters. Currently it's weighing in at 288 278, which is still pretty big.

r=range(81)
def R(A):
 z={} 
 for i in r:
  if 0==A[i]:h=dict((A[j]*(j/9==i/9or j%9==i%9or j/27==i/27and j%9/3==i%9/3),1)for j in r);z[9-len(h)]=h,i
 for l in sorted(z):
  h,i=z[l]
  for j in r[1:10]:
   if(j in h)-1:
    A[i]=j
    if R(A):return A
  A[i]=0;return[]
 return A

Answer 3

r=range(81)
def R(A):
 if(0in A)-1:yield A;return
 def H(i):h=set(A[j]for j in r if j/9==i/9or j%9==i%9or j/27==i/27and j%9/3==i%9/3);return len(h),h,i
 l,h,i=max(H(i)for i in r if not A[i])
 for j in r[1:10]:
  if(j in h)-1:
   A[i]=j
   for S in R(A):yield S
  A[i]=0

269 characters, and it finds all solutions. Usage (not counted in char count):

sixsol = map(int, "300000080001093000040780003093800012000040000520006790600021040000530900030000051")
for S in R(sixsol):
    print S