sudoku in python packaging

Sudoku dalam kemasan python

Selesaikan sudokus bukan dengan python, tetapi dalam paket python.

Menyelesaikan versi paket python dari kebutuhan Anda adalah NP-lengkap, dalam kasus terburuk, paket ini berjalan sangat lambat. Sudokus juga NP-complete, artinya kita bisa menyelesaikan sudokus dengan kemasan python.

Setiap sel dalam kisi sudoku adalah paket sudoku_{x}_{y} (0 diindeks), dan versi (1-9) adalah nilai di bidang tersebut, sehingga Anda dapat menulis pyproject.toml dan paket yang diinstal adalah solusinya.

[ project ]
name = " sudoku "
version = " 1.0.0 "
dependencies = [
    " sudoku_3_1 == 2 " ,
    " sudoku_5_7 == 6 " ,
    " sudoku_0_7 == 5 "
    ...
]

Penggunaan

Anda dapat menulis sudoku sebagai 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

Ubah menjadi persyaratan:

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

Selesaikan dengan pengelola paket favorit Anda, misalnya:

uv pip compile --find-links packages/ --no-annotate --no-header requirements.in > requirements.txt

atau (lambat)

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
[...]

Berikan solusinya:

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

Atau sebagai 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 

Tolok ukur

 $ 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

Waktu dinding tidak jauh berbeda antara sudokus yang saya coba.

Meskipun resolusi ketergantungan adalah NP-lengkap dan algoritme pendukungnya biasanya merupakan semacam pemecah SAT, pada kenyataannya ruang masalahnya jauh lebih kecil: paket biasanya bergantung pada satu rentang dari paket lain, dan rentang tersebut biasanya meningkat secara monoton. Anda hampir tidak pernah mengalami kasus eksponensial, sebagian besar resolusi dengan python dapat dilakukan tanpa harus melakukan kemunduran. Kemacetan kinerjanya adalah mengambil dan menguraikan metadata, dan untuk python secara khusus membangun distribusi sumber.