Résolvez les sudokus non pas en python, mais dans des packages python.
La résolution des versions du package python à partir de vos besoins est NP-complète, dans le pire des cas, elle fonctionne de manière exponentielle. Les sudokus sont également NP-complets, ce qui signifie que nous pouvons résoudre des sudokus avec un packaging python.
Chaque cellule de la grille sudoku est un package sudoku_{x}_{y} (0 indexé), et la version (1-9) est la valeur dans le champ, vous pouvez donc écrire un pyproject.toml et les packages installés sont la solution.
[ project ]
name = " sudoku "
version = " 1.0.0 "
dependencies = [
" sudoku_3_1 == 2 " ,
" sudoku_5_7 == 6 " ,
" sudoku_0_7 == 5 "
...
]Vous pouvez écrire le sudoku au format 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
Convertissez-le en exigences :
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
Résolvez-le avec votre gestionnaire de paquets préféré, par exemple :
uv pip compile --find-links packages/ --no-annotate --no-header requirements.in > requirements.txtou (lent)
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
[...]
Rendre la solution :
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 en 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
Le temps de mur ne variait pas beaucoup entre les sudokus que j'ai essayés.
Bien que la résolution des dépendances soit NP-complète et que leur algorithme de support soit généralement une forme de solveur SAT, en réalité l'espace du problème est beaucoup plus petit : les packages dépendent généralement d'une seule plage d'un autre package, et cette plage augmente généralement de manière monotone. Vous ne rencontrez presque jamais de cas exponentiel, la plupart des résolutions en python peuvent être effectuées sans même revenir en arrière. Le goulot d'étranglement des performances réside plutôt dans la récupération et l'analyse des métadonnées, et pour Python, en créant spécifiquement des distributions sources.
