Python ではなく、Python パッケージで数独を解きます。
要件から Python パッケージのバージョンを解決することは NP 完全ですが、最悪の場合、実行が大幅に遅くなります。数独も NP 完全です。つまり、Python パッケージ化で数独を解くことができます。
sudoku グリッドの各セルはパッケージ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 の場合、特にソース ディストリビューションの構築です。
