Смарт Судоку Гольф

Question

Цель этого вопроса - создать самый короткий не слишком медленный решатель судоку. Это определяется как: не повторяться, когда на доске есть пятна, которые могут быть только одной цифрой .

Вот самое короткое, что у меня есть в 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]);

Это похоже на другие задачи по судоку на гольф, за исключением того, что я хочу устранить ненужную рекурсию. Любой язык приемлем. Задача включена!

Answer 1

Я не особо изменился - алгоритм идентичен, но вот еще несколько микрооптимизаций, которые вы можете внести в свой код Python.

• Нет необходимости для! = 0, 0 - ложь в логическом контексте.

• a, если c иначе 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, i в следующей строке z [l]

• Вы используете s только один раз - нет смысла использовать переменную. Вы также можете избежать использования range (), выбрав вместо этого соответствующий срез r (r [1:10])

• j not in h может стать (j in h)-1 (полагаясь на True == 1 в целочисленном контексте)

• [Редактировать] Вы также можете заменить первый для построения цикла h на конструктор dict и выражение генератора. Это позволяет сжимать логику в одну строку, сохраняя всего 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

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, если не считать пробелы. Если вы просто превратите его в Perl, вы, несомненно, будете лучше, чем мой!