スマート数独ゴルフ

StackOverflow https://stackoverflow.com/questions/216141

  •  03-07-2019
  •  | 
  •  

質問

この質問のポイントは、最短の虐待的に遅くない数独ソルバーを作成することです。これは次のように定義されます：ボード上に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"))

cmd行の入力の一部となる最後の行は、次のように変更できます。

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

これは、不必要な再帰を排除したいことを除いて、他の数独ゴルフの課題と似ています。任意の言語が受け入れられます。チャレンジが始まりました！

役に立ちましたか？

解決

実際にはあまり変更していません-アルゴリズムは同じですが、Pythonコードに対して行うことができる、さらにいくつかのマイクロ最適化があります。

  • ！= 0は不要、0はブール値コンテキストでfalseです。

  • c（c）の場合、bは[a、b] [c]を使用するよりも高価です。短絡が不要な場合、 h [[0、A [j]を使用できます。 ] [j / 9 ..ブール条件の残り] 。さらに良いのは、偽の場合に0を求めるという事実を活用し、ブール値（ 0 * A [j] （つまり0）または 1として扱われる）を掛けることです。 * A [j] （つまり、 A [j] ）。

  • 数字と識別子の間のスペースは省略できます。例：＆quot; 9または＆quot; -＆gt; ＆quot; 9or ＆quot;

  • sorted（）のキーは省略できます。最初の要素でソートしているので、通常のソートでは効果的に同じ順序が生成されます（安定性に依存している場合を除きます）。

  • .items（）呼び出しを省略して、次の行のh、iをz [l]

    • に割り当てるだけで、数バイト節約できます。

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

  • j in h は（j in h）-1 になります（整数コンテキストではTrue == 1に依存）

  • [編集] また、最初のforループのhの構築を、dictコンストラクターとジェネレーター式に置き換えることもできます。これにより、ロジックを1行に圧縮して、合計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に変えれば、間違いなく私のものより良くなるでしょう！

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top