Самый короткий судоку решатель в Python-как это работает?

Ну, вы можете сделать вещи немного легче подправить синтаксис:

def r(a):
  i = a.find('0')
  ~i or exit(a)
  [m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for j in range(81)] or r(a[:i]+m+a[i+1:])for m in'%d'%5**18]
from sys import *
r(argv[1])

очистка немного:

from sys import exit, argv
def r(a):
  i = a.find('0')
  if i == -1:
    exit(a)
  for m in '%d' % 5**18:
    m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3) or a[j] for j in range(81)] or r(a[:i]+m+a[i+1:])

r(argv[1])

Итак, этот скрипт ожидает аргумент командной строки и вызывает функцию r на нем. Если в этой строке нет нулей, r выходит и выводит свой аргумент.

(если передается другой тип объекта, Никто не является эквивалентом прохождения ноль, и любой другой объект печатается системный.stderr и результаты в выход код 1. Особенно, системный.выход ("некоторое сообщение об ошибке") является быстрый способ выхода из программы, когда возникает ошибка. Видеть http://www.python.org/doc/2.5.2/lib/module-sys.html)

Я думаю, это означает, что нули соответствуют открытым пространствам, и головоломка без нулей решена. Тогда есть это неприятное рекурсивное выражение.

петля интересная:for m in'%d'%5**18

почему 5**18? Оказывается, что '%d'%5**18 значение '3814697265625'. Это строка, которая имеет каждую цифру 1-9 по крайней мере один раз, так что, возможно, он пытается разместить каждый из них. На самом деле, похоже, что это то, что r(a[:i]+m+a[i+1:]) делает: рекурсивно вызывая r, с первым пробелом, заполненным цифрой из этой строки. Но это происходит только в том случае, если предыдущее выражение ложно. Давайте посмотрим на это:

m in [(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3) or a[j] for j in range(81)]

таким образом, размещение выполняется только в том случае, если m не находится в этом списке монстров. Каждый элемент является либо числом (если первое выражение ненулевой) или символ (если первое выражение равно нулю). m исключается как возможная подстановка, если она появляется как символ, что может произойти только в том случае, если первое выражение равно нулю. Когда выражение равно нулю?

он имеет три части, которые умножаются:

• (i-j)%9 который равен нулю, если i и j кратны 9 друг от друга, т. е. один и тот же столбец.
• (i/9^j/9) который равен нулю, если i/9 == j / 9, т. е. та же строка.
• (i/27^j/27|i%9/3^j%9/3) который равен нулю, если оба они равны нулю:
• • i/27^j^27 который равен нулю, если i/27 == j / 27, т. е. тот же блок из трех строк
• • i%9/3^j%9/3 который равен нулю, если i%9/3 = = j%9/3, т. е. тот же блок из трех столбцов

если любой из этих трех частей равна нулю, то все выражение равно нулю. Другими словами, если i и j совместно используют строку, столбец или блок 3x3, то значение j не может быть используется в качестве кандидата на пробел в i. Ага!

from sys import exit, argv
def r(a):
  i = a.find('0')
  if i == -1:
    exit(a)
  for m in '3814697265625':
    okay = True
    for j in range(81):
      if (i-j)%9 == 0 or (i/9 == j/9) or (i/27 == j/27 and i%9/3 == j%9/3):
        if a[j] == m:
          okay = False
          break
    if okay:
      # At this point, m is not excluded by any row, column, or block, so let's place it and recurse
      r(a[:i]+m+a[i+1:])

r(argv[1])

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

не используя никаких эвристик, это не особенно эффективно. Я взял эту головоломку из Википедии (http://en.wikipedia.org/wiki/Sudoku):

$ time python sudoku.py 530070000600195000098000060800060003400803001700020006060000280000419005000080079
534678912672195348198342567859761423426853791713924856961537284287419635345286179

real    0m47.881s
user    0m47.223s
sys 0m0.137s

добавление: как бы я переписал его как программист обслуживания (эта версия имеет около 93x ускорение :)

import sys

def same_row(i,j): return (i/9 == j/9)
def same_col(i,j): return (i-j) % 9 == 0
def same_block(i,j): return (i/27 == j/27 and i%9/3 == j%9/3)

def r(a):
  i = a.find('0')
  if i == -1:
    sys.exit(a)

  excluded_numbers = set()
  for j in range(81):
    if same_row(i,j) or same_col(i,j) or same_block(i,j):
      excluded_numbers.add(a[j])

  for m in '123456789':
    if m not in excluded_numbers:
      # At this point, m is not excluded by any row, column, or block, so let's place it and recurse
      r(a[:i]+m+a[i+1:])

if __name__ == '__main__':
  if len(sys.argv) == 2 and len(sys.argv[1]) == 81:
    r(sys.argv[1])
  else:
    print 'Usage: python sudoku.py puzzle'
    print '  where puzzle is an 81 character string representing the puzzle read left-to-right, top-to-bottom, and 0 is a blank'