스마트 스도쿠 골프

Question

이 질문의 요지는 가장 짧게 을 만들며, 악의적으로 느림은 아닙니다. 스도쿠 (Sudoku) 해결사입니다. 이것은 다음과 같이 정의됩니다 : 한 자리 수만있을 수있는 스폿이있는 경우 재발행하지 않습니다. 여기

최단 내가 파이썬 원경 가지고있다 :

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

이 :

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

I는 CMD 라인 입력의 일부로 수행 마지막 라인, 이는 변경 될 수있다 불필요한 재귀를 제거하고 싶다는 점을 제외하면 다른 스도쿠 골프 과제와 유사합니다. 모든 언어가 허용됩니다. 도전 과제는 위에 있습니다!

Answer 1

나는 알고리즘을 변경하지 않았지만 알고리즘은 동일하지만 파이썬 코드에 추가 할 수있는 몇 가지 미세 최적화가 있습니다.

• 필요 없음을! = 0, 0 부울 컨텍스트에서 false입니다.

• a 단락이 필요없는 경우 [b] [c]를 사용하는 것보다 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() 호출을 생략하고 z [l]에 다음 줄에 h, i를 할당하면 바이트 수가 줄어 듭니다.

• 변수를 사용할 때만 s를 한 번 사용합니다. 또한

• (정수 컨텍스트 트루 == 1에 의존) (j in h)-1 될 수 대신 R 적절한 슬라이스를 선택하여 (R의 [1시 10분])

• j not in h 범위()를 사용하지 않도록 할 [편집] 또한 첫 번째 for 루프의 h 구성을 dict 생성자 및 생성자 표현식으로 바꿀 수 있습니다. 이렇게하면 논리를 한 줄로 압축하여 총 10 바이트를 절약 할 수 있습니다.

더 일반적으로 중첩 수준을 줄이기 위해 알고리즘을 변경하는 방법에 대해 생각하고 싶을 것입니다. 모든 수준은 파이썬에서 한 줄에 추가 바이트를 제공하며 누적됩니다.

여기에 내가 지금까지 가지고있는 것이 있습니다 (필자는 들여 쓰기 당 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 

Answer 2

난 그냥 조금 여기에 파이썬을 손질했습니다 당신이 공백을 계산하지 않는 경우

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

이 250, 무거운 410 자입니다. 당신이 perl로 바꾸면 틀림없이 내 것보다 낫다.

Answer 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