لعبة غولف سودوكو الذكية

Question

الهدف من هذا السؤال هو إنشاء الأقصر ليست بطيئة بشكل مسيئ سودوكو حلالا.يتم تعريف هذا على النحو التالي: لا تتكرر عندما تكون هناك نقاط على اللوحة يمكن أن تتكون من رقم واحد فقط.

هنا هو أقصر ما لدي حتى الآن في بيثون:

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]);

هذا مشابه لتحديات سودوكو جولف الأخرى، باستثناء أنني أريد التخلص من التكرار غير الضروري.أي لغة مقبولة.التحدي قائم!

Answer 1

لم أقم بإجراء تغيير كبير حقًا - الخوارزمية متطابقة ، ولكن فيما يلي بعض الأمراض الدقيقة التي يمكنك إجراؤها على رمز Python الخاص بك.

• لا حاجة! = 0 ، 0 خاطئة في سياق منطقي.

• إذا كان C else B أغلى من استخدام [A ، B] [C] إذا لم تكن بحاجة إلى دائرة قصيرة ، فإنك يمكنك استخدامها h[ [0,A[j]][j/9.. rest of boolean condition]. والأفضل من ذلك هو استغلال حقيقة أنك تريد 0 في الحالة الخاطئة ، وتكاثر ذلك بالقيمة المنطقية (تعامل على أنها أيضًا 0*A[j] (أي 0) أو 1*A[j] (بمعنى آخر. A[j]).

• يمكنك حذف المساحات بين الأرقام والمعرفات. على سبيل المثال "9 or" -> "9or"

• يمكنك حذف مفتاح الفرز (). نظرًا لأنك تقوم بفرز العنصر الأول ، فإن النوع العادي ينتج نفس الترتيب بشكل فعال (إلا إذا كنت تعتمد على الاستقرار ، وهو ما لا يبدو)

• يمكنك حفظ اثنين من البايتات عن طريق حذف مكالمة .items () ، وتعيين H ، أنا في السطر التالي إلى z [l

• يمكنك فقط استخدام S مرة واحدة - لا جدوى من استخدام متغير. يمكنك أيضًا تجنب استخدام Range () عن طريق تحديد الشريحة المناسبة لـ R بدلاً من ذلك (R [1:10])

• j not in h يمكن أن تصبح (j in h)-1 (الاعتماد على صحيح == 1 في سياق عدد صحيح)

• يحرر يمكنك أيضًا استبدال الأول لبناء Loop لـ H بمنشئ DICT وتعبير المولد. يتيح لك ذلك ضغط المنطق على سطر واحد ، مما يوفر 10 بايت في المجموع.

بشكل عام ، ربما تريد التفكير في طرق لتغيير الخوارزمية لتقليل مستويات التعشيش. كل مستوى يعطي بايت إضافي لكل سطر داخل بيثون ، والذي يتراكم.

إليك ما حصلت عليه حتى الآن (لقد تحولت إلى مساحة واحدة لكل مسافة قريبة حتى تتمكن من الحصول على صورة دقيقة للشخصيات المطلوبة. 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

Answer 2

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

Answer 3

لقد قمت للتو بقلص الثعبان قليلاً هنا:

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 إذا لم تحسب مساحة بيضاء. إذا قمت فقط بتحويلها إلى بيرل ، فستكون بلا شك أفضل من لي!