智能数独高尔夫

Question

这个问题的目的是要创建一个最短的但不至于太慢的数独解题器。这里的定义是：当棋盘上有只能是一个数字的空格时，不要使用递归。

这是我目前在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"))

最后一行我认为是命令行输入的一部分，可以改成：

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

这个挑战和其他数独代码挑战类似，不过我想要避免不必要的递归。任何编程语言都可以。挑战开始了！

Answer 1

我刚把这段Python代码稍微简化了一下：

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

这段代码有410个字符，如果不算空格的话就是250个字符。如果你把它转成Perl语言，肯定会比我写得更好！

Answer 2

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个字符，而且它能找到所有的解决方案。使用方法（不算在字符数里）：

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

Answer 3

其实我没有做太大的改动，算法还是一样的，不过这里有一些小技巧可以让你的Python代码更高效。

• 没有必要写成 !=0，因为在布尔上下文中，0本身就是假。

• 用a if c else b会比用[a,b][c]更耗资源，尤其是当你不需要短路求值的时候。所以你可以用h[ [0,A[j]][j/9.. 其他布尔条件]。更好的方法是利用你在假情况下想要0的事实，可以通过乘以布尔值来实现（布尔值要么是0*A[j]（即0），要么是1*A[j]（即A[j]））。

• 数字和标识符之间可以省略空格。比如"9 or"可以写成"9or"。

• 在调用sorted()时可以省略key参数。因为你是根据第一个元素排序，普通的排序基本上会得到相同的顺序（除非你依赖稳定性，但看起来你并不需要）。

• 可以省去.items()的调用，直接在下一行把h和i赋值给z[l]，这样可以节省几个字节。

• 你只用到s一次，没必要用变量。你也可以通过选择r的合适切片来避免使用range()（比如用r[1:10]）。

• j not in h可以改成(j in h)-1（这依赖于在整数上下文中True等于1）。

• [编辑]你还可以用字典构造器和生成器表达式来替代第一个for循环构造h，这样可以把逻辑压缩到一行，总共节省10个字节。

更一般来说，你可能需要考虑如何改变算法以减少嵌套层数。每增加一层嵌套，Python中每行就会多出一个字节，这样累积起来会很可观。

这是我目前的成果（我把每个缩进改成1个空格，这样你可以准确看到需要的字符数。目前的字节数是288 278，还是挺大的。

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