2

この質問のポイントは、乱暴に遅くない最短の数独ソルバーを作成することです。これは次のように定義されています:ボード上に 1 桁しかない可能性があるスポットがある場合は再帰しないでください。

これは私がこれまで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]);

これは、不必要な再帰を排除したいという点を除けば、他の数独ゴルフ チャレンジと似ています。どの言語でも構いません。チャレンジ開始！

4

3 に答える 3

3

私は実際にはあまり変更を加えていません-アルゴリズムは同じですが、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]さらに良いのは、falseの場合に0が必要であるという事実を利用して、ブール値（（ ie。0）または1*A[j]（ie。 ）として扱われる）を掛けることA[j]です。

  • 数字と識別子の間のスペースは省略できます。例： " 9 or"-> " 9or"

  • sort（）のキーは省略できます。最初の要素で並べ替えているので、通常の並べ替えでは、実質的に同じ順序が生成されます（安定性に依存している場合を除き、そのようには見えません）。

  • .items（）呼び出しを省略して、次の行のh、iをz [l]に割り当てるだけで、数バイト節約できます。

  • sは1回だけ使用します。変数を使用しても意味がありません。代わりにrの適切なスライスを選択することで、range（）の使用を回避することもできます（r [1:10]）

  • j not in hになる可能性があります(j in h)-1（整数コンテキストでTrue == 1に依存）

  • [編集]最初のforループのhの構成を、dictコンストラクターとジェネレーター式に置き換えることもできます。これにより、ロジックを1行に圧縮して、合計10バイトを節約できます。

より一般的には、ネストのレベルを下げるためにアルゴリズムを変更する方法を考えたいと思うでしょう。すべてのレベルで、Python内の1行に1バイトが追加され、累積されます。

これが私がこれまでに得たものです（必要な文字の正確な画像を取得できるように、インデントごとに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 に答える