python - 智能数独高尔夫

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

我把最后一行作为cmd行输入的一部分，可以改成:

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

这与其他数独高尔夫挑战类似，只是我想消除不必要的递归。任何语言都可以。挑战开始了!

Answer 1

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

• 不需要 !=0，0 在 bool 上下文中为假。

• a if c else b 如果不需要短路，则比使用 [a,b][c] 更昂贵，因此您可以使用 h[ [0,A[j] ][j/9.. bool 条件的其余部分]。更好的办法是利用你在错误情况下想要 0 的事实，然后乘以 bool 值(被视为 0*A[j](即 0)或 1 *A[j](即 A[j])。

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

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

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

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

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

  <

• [编辑] 您还可以将 h 的第一个 for 循环构造替换为字典构造函数和生成器表达式。这让您可以将逻辑压缩到一行，总共节省 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