2

这个问题的重点是创建最短且不滥用缓慢的数独求解器。这被定义为：当棋盘上有可能只有一位数的点时，不要递归。

这是迄今为止我在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"))

我将最后一行作为 cmd 行输入的一部分，它可以更改为：

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

这类似于其他数独高尔夫挑战，只是我想消除不必要的递归。任何语言都可以接受。挑战来了！

4

3 回答 3

3

我并没有真正做出太大的改变——算法是相同的，但是这里有一些你可以对你的 python 代码进行的进一步的微优化。

  • 不需要 !=0, 0 在布尔上下文中为假。

  • a if c else b 如果不需要短路，则比使用 [a,b][c] 更昂贵，因此您可以使用h[ [0,A[j]][j/9.. rest of boolean condition]. 更好的是利用您在错误情况下想要 0 的事实，然后乘以布尔值（被视为0*A[j](ie. 0) 或1*A[j](ie. A[j])。

  • 您可以省略数字和标识符之间的空格。例如“ 9 or”->“ 9or”

  • 您可以省略 sorted() 的键。由于您正在对第一个元素进行排序，因此正常排序将有效地产生相同的顺序（除非您依赖于稳定性，它看起来不像）

  • 您可以通过省略 .items() 调用来节省几个字节，只需将下一行中的 h,i 分配给 z[l]

  • 您只使用 s 一次 - 使用变量没有意义。您还可以通过选择适当的 r 切片来避免使用 range() (r[1:10])

  • j not in h可以变成(j in h)-1（在整数上下文中依赖 True == 1）

  • [编辑]您还可以将第一个 for 循环的 h 构造替换为 dict 构造函数和生成器表达式。这使您可以将逻辑压缩到一行，总共节省 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
于 2008-10-19T22:54:37.580 回答
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 个字符，它会找到所有解决方案。用法（不计入字符数）：

sixsol = map(int, "300000080001093000040780003093800012000040000520006790600021040000530900030000051")
for S in R(sixsol):
    print S
于 2008-10-20T05:12:33.433 回答
2

我刚刚在这里修剪了一下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 你无疑会比我的更好！

于 2008-10-19T16:19:42.557 回答