题
这个问题的重点是创建最短的 不慢得过分 数独解算器。这定义为: 当棋盘上有只能是一位数字的点时不要递归.
这是我迄今为止在 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]);
这与其他数独高尔夫挑战类似,只是我想消除不必要的递归。任何语言都可以接受。挑战开始了!
解决方案
我并没有真正做太多的改变——算法是相同的,但这里有一些你可以对你的 python 代码进行的进一步的微观优化。
不需要 !=0,0 在布尔上下文中为 false。
如果不需要短路,则 a if c else b 比使用 [a,b][c] 更昂贵,因此可以使用
h[ [0,A[j]][j/9.. rest of boolean condition]
. 。更好的是利用这样一个事实,即在 false 情况下您想要 0,因此乘以布尔值(视为0*A[j]
(IE。0) 或1*A[j]
(IE。A[j]
).您可以省略数字和标识符之间的空格。例如“
9 or
" -> "9or
"您可以省略排序()的键。由于您对第一个元素进行排序,因此普通排序将有效地产生相同的顺序(除非您依赖于稳定性,但它看起来并不像)
您可以通过省略 .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
其他提示
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
我刚刚在这里修剪了一下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,你无疑会比我的更好!