Ответ 1
Ну, вы можете сделать немного проще, установив синтаксис:
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])
Хорошо, поэтому этот script ожидает аргумент командной строки и вызывает на нем функцию r. Если в этой строке нет нулей, r завершает и распечатывает свой аргумент.
(Если передан другой тип объекта, Ни один из них не равен нулю, и любой другой объект печатается на sys.stderr и приводит к выходу код 1. В частности, sys.exit( "некоторое сообщение об ошибке" ) является быстрый способ выхода из программы, когда возникает ошибка. Видеть 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 исключается как возможная подстановка, если она появляется как символ, что может произойти только в том случае, если первое выражение равно нулю. Когда выражение 0?
Он состоит из трех частей, которые умножаются:
-
(i-j)%9, который равен нулю, если я и 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, т.е. тот же блок из трех столбцов
-
Если любая из этих трех частей равна нулю, все выражение равно нулю. Другими словами, если я и j делят строку, столбец или блок 3x3, то значение j не может использоваться в качестве кандидата для пробела в i. Aha!
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 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
Добавление: как я буду переписывать его в качестве программиста по обслуживанию (эта версия имеет примерно 93-кратное ускорение:)
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 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'