Ну, вы можете немного упростить ситуацию, исправив синтаксис:
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 завершается и выводит аргумент.
(Если передан другой тип объекта,
Ни один не эквивалентен прохождению нуля,
и любой другой объект печатается на
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 исключается как возможная замена, если он появляется в виде символа, что может произойти, только если первое выражение равно нулю. Когда выражение равно нулю?
Он состоит из трех частей:
(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. 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'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
Приложение: Как бы я переписал его как программиста по техническому обслуживанию (эта версия имеет ускорение в 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'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'