Решайте судоку не в Python, а в пакетах Python.
Решение версий пакета Python в соответствии с вашими требованиями является NP-полным, в худшем случае оно выполняется экспоненциально медленно. Судоку также являются NP-полными, что означает, что мы можем решать судоку с помощью упаковки Python.
Каждая ячейка в сетке судоку представляет собой пакет sudoku_{x}_{y} (индексирован 0), а версия (1–9) — это значение в поле, поэтому вы можете написать pyproject.toml, и установленные пакеты будут решение.
[ project ]
name = " sudoku "
version = " 1.0.0 "
dependencies = [
" sudoku_3_1 == 2 " ,
" sudoku_5_7 == 6 " ,
" sudoku_0_7 == 5 "
...
]Вы можете написать судоку в формате csv:
5,3,_,_,7,_,_,_,_
6,_,_,1,9,5,_,_,_
_,9,8,_,_,_,_,6,_
8,_,_,_,6,_,_,_,3
4,_,_,8,_,3,_,_,1
7,_,_,_,2,_,_,_,6
_,6,_,_,_,_,2,8,_
_,_,_,4,1,9,_,_,5
_,_,_,_,8,_,_,7,9
Преобразуйте его в требования:
python csv_to_requirements.py sudoku.csv requirements.in sudoku_0_0 == 5
sudoku_1_0 == 3
[...]
sudoku_7_8 == 7
sudoku_8_8 == 9
Решите проблему с помощью вашего любимого менеджера пакетов, например:
uv pip compile --find-links packages/ --no-annotate --no-header requirements.in > requirements.txtили (медленно)
pip-compile --find-links packages/ --no-annotate --no-header requirements.in -o requirements.txt sudoku-0-0==5
sudoku-0-1==6
sudoku-0-2==1
sudoku-0-3==8
sudoku-0-4==4
[...]
Отобразите решение:
python render_solution.py requirements.txt 5,3,4,6,7,8,9,1,2
6,7,2,1,9,5,3,4,8
1,9,8,3,4,2,5,6,7
8,5,9,7,6,1,4,2,3
4,2,6,8,5,3,7,9,1
7,1,3,9,2,4,8,5,6
9,6,1,5,3,7,2,8,4
2,8,7,4,1,9,6,3,5
3,4,5,2,8,6,1,7,9
Или как однострочник:
$ python csv_to_requirements.py royle.csv - | uv pip compile --find-links packages/ --no-annotate --no-header - | python render_solution.py -
Resolved 81 packages in 126ms
5,3,4,6,7,8,9,1,2
6,7,2,1,9,5,3,4,8
1,9,8,3,4,2,5,6,7
8,5,9,7,6,1,4,2,3
4,2,6,8,5,3,7,9,1
7,1,3,9,2,4,8,5,6
9,6,1,5,3,7,2,8,4
2,8,7,4,1,9,6,3,5
3,4,5,2,8,6,1,7,9 $ hyperfine --warmup 5 "uv pip compile --find-links packages/ --no-index --no-annotate --no-header requirements.in"
Benchmark 1: uv pip compile --find-links packages/ --no-index --no-annotate --no-header requirements.in
Time (mean ± σ): 29.7 ms ± 1.6 ms [User: 29.9 ms, System: 21.0 ms]
Range (min … max): 27.5 ms … 35.0 ms 97 runs
Время стены не сильно различалось в разных судоку, которые я пробовал.
Хотя разрешение зависимостей является NP-полным, а их алгоритм поддержки обычно представляет собой некоторую форму решателя SAT, в действительности проблемное пространство намного меньше: пакеты обычно зависят от одного диапазона другого пакета, и этот диапазон обычно монотонно увеличивается. Вы почти никогда не сталкиваетесь с экспоненциальным случаем, большую часть разрешения в Python можно выполнить даже без возврата. Вместо этого узким местом производительности является выборка и анализ метаданных, а для Python — специальное создание исходных дистрибутивов.
