智能數獨高爾夫

這個問題的關鍵是要創造最短的不要太慢數獨求解器。這被定義爲：當板上有斑點時，不能遞歸，只能有一個數字。智能數獨高爾夫

這裏是最短的我到目前爲止在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]);

這與其他數獨高爾夫挑戰類似，只是我想消除不必要的遞歸。任何語言都可以接受。挑戰在於！

來源

2008-10-19 Claudiu

我沒有真正做出太多的改變 - 算法是相同的，但這裏有一些進一步的微觀優化，你可以對你的Python代碼。

不需要！= 0,0在布爾上下文中爲false。
a if c else b比使用[a，b] [c]更貴，如果不需要短路，則可以使用h[ [0,A[j]][j/9.. rest of boolean condition]。更妙的是布爾值（無論是0*A[j]（即0）或1*A[j]（即A[j]處理）利用的事實，你在錯誤的情況下，想要0，所以繁殖。
可以省略空間數字和標識符之間例如「9 or」 - >「9or」
可以省略鍵排序（）既然你排序的第一個元素上，一個正常的排序將有效地產生相同的順序（除非你依靠穩定性，它看起來不像）
你可以保存一對夫婦通過省略.items（）調用，並且只將h，i分配給下一行中的字節[z]
您只使用s一次 - 使用變量沒有意義。還可以避免使用範圍（）通過選擇r的適當切片代替（R [1:10]）
j not in h可以成爲(j in h)-1（在整數上下文上真== 1依託）
[編輯]你也可以用一個字典構造函數和一個生成器表達式替換循環的第一個h的構造。這可以讓您將邏輯壓縮到一行，總共節省10個字節。

更一般地，您可能想要考慮更改算法以降低嵌套級別的方法。每個級別在python中每行給出一個額外的字節，這會累積。

下面是我得到了什麼至今（我切換到每縮進1個空間，這樣就可以得到所需的字符的準確描述。目前它在 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-19 22:54:37 Brian

不錯它肯定從我的版本修剪下來 - 不想到了這些微選擇技巧。現在我已經創建了一個更大的版本，可以更有效地工作，並獲得數獨的所有解決方案，但這正在改變問題規範。 – Claudiu 2008-10-19 23:47:53

我剛剛修剪蟒蛇有點這裏：

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-19 16:19:42 Claudiu

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-20 05:12:33 Claudiu

智能數獨高爾夫

回答

相關問題