Resolva sudokus não em python, mas em pacotes python.
Resolver as versões do pacote python de acordo com seus requisitos é NP-completo; na pior das hipóteses, ele é exponencialmente lento. Os sudokus também são NP-completos, o que significa que podemos resolver sudokus com empacotamento python.
Cada célula na grade sudoku é um pacote sudoku_{x}_{y} (0 indexado), e a versão (1-9) é o valor no campo, então você pode escrever um pyproject.toml e os pacotes instalados são a solução.
[ project ]
name = " sudoku "
version = " 1.0.0 "
dependencies = [
" sudoku_3_1 == 2 " ,
" sudoku_5_7 == 6 " ,
" sudoku_0_7 == 5 "
...
]Você pode escrever o sudoku como 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
Converta-o em requisitos:
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
Resolva com seu gerenciador de pacotes favorito, por exemplo:
uv pip compile --find-links packages/ --no-annotate --no-header requirements.in > requirements.txtou (lento)
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
[...]
Renderize a solução:
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
Ou como oneliner:
$ 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
O tempo de parede não variou muito entre os sudokus que experimentei.
Embora a resolução de dependências seja NP-completa e seu algoritmo de apoio seja geralmente alguma forma de solucionador SAT, na realidade o espaço do problema é muito menor: os pacotes geralmente dependem de um único intervalo de outro pacote, e esse intervalo geralmente aumenta monotonicamente. Você quase nunca se depara com um caso exponencial; a maior parte da resolução em python pode ser feita sem sequer voltar atrás. O gargalo de desempenho é, em vez disso, buscar e analisar metadados e, para python, construir especificamente distribuições de origem.
