Solving Sudoku in Python Packaging

I love this so much. I dug around a bit and figured out how it works - I have an explanation (with an illustrative diagram) here: <a href="https:&#x2F;&#x2F;simonwillison.net&#x2F;2024&#x2F;Oct&#x2F;21&#x2F;sudoku-in-python-packaging&#x2F;" rel="nofollow">https:&#x2F;&#x2F;simonwillison.net&#x2F;2024&#x2F;Oct&#x2F;21&#x2F;sudoku-in-python-packa...</a><p>Figuring out how it works is a great way to learn a bit more about how Python packaging works under the hood. I learned that .whl files contain a METADATA file listing dependency constraints as &quot;Requires-Dist&quot; rules.<p>I ran a speed comparison too. Using the uv pip resolver it took 0.24s - with the older pip-compile tool it took 17s.

That&#x27;s why it feels like installing a ML repo is like sudoku. You install everything and at the last step you realize your neural net uses FlashAttention2 which only works on NVIDIA compute version that is not deployed in your cloud VM and you need to start over from scratch.

Here’s the same thing in Poetry (2022): <a href="https:&#x2F;&#x2F;www.splitgraph.com&#x2F;blog&#x2F;poetry-dependency-resolver-sudoku" rel="nofollow">https:&#x2F;&#x2F;www.splitgraph.com&#x2F;blog&#x2F;poetry-dependency-resolver-s...</a>

&gt; Solving the versions of python package from your requirements is NP-complete, in the worst case it runs exponentially slow. Sudokus are also NP-complete, which means we can solve sudokus with python packaging.<p>Is that actually sufficient? Can every system that’s solving something that’s NP-complete solve every other NP-complete problem?

No way pip actually is a really inefficient SAT solver!

This is BRILLIANT ! I knew of a trend to implement lots of different things at compile-time (in Scala and Haskell communities at least) - definitely fun and quirky, but it never seemed that &quot;special&quot;. This one, it has an air of old-school computer magic around it, probably because it is so elegant and simple.

See also this 2008 post using Debian package system to solve Sudoku:<p><a href="https:&#x2F;&#x2F;web.archive.org&#x2F;web&#x2F;20160326062818&#x2F;http:&#x2F;&#x2F;algebraicthunk.net&#x2F;~dburrows&#x2F;blog&#x2F;entry&#x2F;package-management-sudoku&#x2F;" rel="nofollow">https:&#x2F;&#x2F;web.archive.org&#x2F;web&#x2F;20160326062818&#x2F;http:&#x2F;&#x2F;algebraict...</a>

but how does it know the constraints?

This is type of cool hacking I like to see. Kudos! (Or better, Sukodus :) )

How did you even think of that? Nice!

This is a hack.

Now, in MicroLisp, Common Lisp and maybe Emacs&#x27; Elisp too:<p><a href="http:&#x2F;&#x2F;www.ulisp.com&#x2F;show?33J9" rel="nofollow">http:&#x2F;&#x2F;www.ulisp.com&#x2F;show?33J9</a>