Умный Гольф в судоку

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 равно false в логическом контексте.

• a если c, то b обходится дороже, чем использование [a, b] [c] если вам не нужно короткое замыкание, следовательно, вы можете использовать h[ [0,A[j]][j/9.. rest of boolean condition].Еще лучше использовать тот факт, что вы хотите 0 в случае false, и поэтому умножить на логическое значение (рассматриваемое как либо 0*A[j] (то есть.0) или 1*A[j] (то есть. A[j]).

• Вы можете опустить пробелы между цифрами и идентификаторами.например "9 or" -> "9or"

• Вы можете опустить ключ в sorted().Поскольку вы сортируете по первому элементу, обычная сортировка фактически приведет к тому же порядку (если только вы не полагаетесь на стабильность, на которую это не похоже)

• Вы можете сэкономить пару байт, опустив вызов .items() и просто присвоив h,i в следующей строке z[l]

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

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

• [Править] Вы также можете заменить конструкцию h из первого цикла for конструктором 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, вы, несомненно, будете лучше, чем у меня!