sudoku in python packaging

Sudoku en embalaje de Python

Resuelva sudokus no en Python, sino en paquetes de Python.

Resolver las versiones del paquete Python a partir de sus requisitos es NP-completo; en el peor de los casos, se ejecuta exponencialmente lento. Los sudokus también son NP completos, lo que significa que podemos resolver sudokus con empaquetado en Python.

Cada celda en la cuadrícula de sudoku es un paquete sudoku_{x}_{y} (0 indexado), y la versión (1-9) es el valor en el campo, por lo que puede escribir un pyproject.toml y los paquetes instalados son la solución.

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

Uso

Puedes escribir el 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

Conviértalo a 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

Resuélvelo con tu administrador de paquetes favorito, por ejemplo:

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

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

Representa la solución:

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

O como una línea:

$ 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 

Punto de referencia

 $ 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

El tiempo de pared no varió mucho entre los sudokus que probé.

Si bien la resolución de dependencias es NP-completa y su algoritmo de respaldo suele ser algún tipo de solucionador SAT, en realidad el espacio del problema es mucho más pequeño: los paquetes generalmente dependen de un único rango de otro paquete, y ese rango generalmente aumenta de manera monótona. Casi nunca te encuentras con un caso exponencial, la mayor parte de la resolución en Python se puede realizar sin siquiera retroceder. En cambio, el cuello de botella en el rendimiento es buscar y analizar metadatos y, en el caso de Python, crear distribuciones de origen específicamente.