Lösen Sie Sudokus nicht in Python, sondern in Python-Paketen.
Das Auflösen der Versionen des Python-Pakets anhand Ihrer Anforderungen ist NP-vollständig und läuft im schlimmsten Fall exponentiell langsam. Sudokus sind außerdem NP-vollständig, was bedeutet, dass wir Sudokus mit Python-Paketierung lösen können.
Jede Zelle im Sudoku-Raster ist ein Paket sudoku_{x}_{y} (0 indiziert), und die Version (1-9) ist der Wert im Feld, sodass Sie eine pyproject.toml schreiben können und die installierten Pakete sind die Lösung.
[ project ]
name = " sudoku "
version = " 1.0.0 "
dependencies = [
" sudoku_3_1 == 2 " ,
" sudoku_5_7 == 6 " ,
" sudoku_0_7 == 5 "
...
]Sie können das Sudoku als CSV schreiben:
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
Konvertieren Sie es in Anforderungen:
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
Lösen Sie es mit Ihrem bevorzugten Paketmanager, z. B.:
uv pip compile --find-links packages/ --no-annotate --no-header requirements.in > requirements.txtoder (langsam)
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
[...]
Rendern Sie die Lösung:
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
Oder als 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
Die Wandzeit variierte zwischen den Sudokus, die ich ausprobiert habe, kaum.
Während die Abhängigkeitsauflösung NP-vollständig ist und ihr zugrunde liegender Algorithmus normalerweise eine Art SAT-Löser ist, ist der Problemraum in Wirklichkeit viel kleiner: Pakete hängen normalerweise von einem einzelnen Bereich eines anderen Pakets ab, und dieser Bereich nimmt normalerweise monoton zu. Sie stoßen fast nie auf einen exponentiellen Fall, die meisten Auflösungen in Python können ohne Zurückverfolgen durchgeführt werden. Der Leistungsengpass besteht stattdessen im Abrufen und Parsen von Metadaten und für Python insbesondere im Erstellen von Quelldistributionen.
