9 ms·

Solving Sudoku in Python Packaging

305 points by Yenrabbit 2y ago

niyonx 2y ago
How did you even think of that? Nice!
yochem 2y ago
No way pip actually is a really inefficient SAT solver!
- stabbles 2y ago
  For a long time it was not because there was no backtracking. Now it is just an exhaustive, recursive search: for the current package try using versions from newest to oldest, enqueue its dependencies, if satisfied return, if conflict continue.
  - taeric 2y ago
    If there was no backtracking, that implies it couldn't solve every sudoku? That is rather amusing with the implication that it couldn't solve every dependency, as well?
- fernandotakai 2y ago
  uv actually talks about this in their resolver docs https://docs.astral.sh/uv/reference/resolver-internals/ https://docs.astral.sh/uv/reference/resolver-internals/
ziofill 2y ago
but how does it know the constraints?
- jsnell 2y ago
  The constraints are going to be static and independent of the puzzle. So I expect they're encoded in the package dependencies. So for example version 1 of the package sudoku_0_0 will conflict with all of: version 1 of sudoku_[0-8]_0; version 1 of sudoku_0_[0-8]; version 1 of [012]_ [012].
  - roywiggins 2y ago
    generate_packages makes it moderately clear: https://github.com/konstin/sudoku-in-python-packaging/blob/main/generate_packages.py https://github.com/konstin/sudoku-in-python-packaging/blob/m...
- thangngoc89 2y ago
  This is the content of sudoku_0_0-1-py3-none-any.whl. So when the (0,0) cell is 1, none of the cells in the same row, column and subgrid should be 1. Requires-Dist: sudoku_0_1 != 1 Requires-Dist: sudoku_0_2 != 1 Requires-Dist: sudoku_0_3 != 1 Requires-Dist: sudoku_0_4 != 1 Requires-Dist: sudoku_0_5 != 1 Requires-Dist: sudoku_0_6 != 1 Requires-Dist: sudoku_0_7 != 1 Requires-Dist: sudoku_0_8 != 1 Requires-Dist: sudoku_1_0 != 1 Requires-Dist: sudoku_2_0 != 1 Requires-Dist: sudoku_3_0 != 1 Requires-Dist: sudoku_4_0 != 1 Requires-Dist: sudoku_5_0 != 1 Requires-Dist: sudoku_6_0 != 1 Requires-Dist: sudoku_7_0 != 1 Requires-Dist: sudoku_8_0 != 1 Requires-Dist: sudoku_0_1 != 1 Requires-Dist: sudoku_0_2 != 1 Requires-Dist: sudoku_1_0 != 1 Requires-Dist: sudoku_1_1 != 1 Requires-Dist: sudoku_1_2 != 1 Requires-Dist: sudoku_2_0 != 1 Requires-Dist: sudoku_2_1 != 1 Requires-Dist: sudoku_2_2 != 1
- IshKebab 2y ago
  Yeah they missed out the actual interesting bit from the readme...
simonw 2y ago
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: https://simonwillison.net/2024/Oct/21/sudoku-in-python-packaging/ https://simonwillison.net/2024/Oct/21/sudoku-in-python-packa... 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 "Requires-Dist" rules. I ran a speed comparison too. Using the uv pip resolver it took 0.24s - with the older pip-compile tool it took 17s.
- seanw444 2y ago
  Wow, uv really is fast.
  - jebebeebehhe 2y ago
    As is simonw writing that post in under 60m assuming he first saw the concept here on HN.
    - deleted 2y ago
      [deleted]
    - Medox 2y ago
      Using the simonw resolver is took under 3600s *
    - simonw 2y ago
      Nah I wrote this one a couple of days ago when I first saw the Sudoku solving project on Mastodon.
      - jeanlucas 2y ago
        Thank you, I was going to point out the post on your blog has date of publication lol
- c10n3x 2y ago
visarga 2y ago
That'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.
- austinjp 2y ago
  This describes the day I wasted on Monday before I gave up and wrote some damn deterministic code instead of using some damn AI.
- hskalin 2y ago
  Sometimes I just change the version of the package in requirements to fit with others and pray that it works out (a few times it does)
- nicman23 2y ago
  honestly if the ml does not have a docker image - not compose no build an image- i do not even bother any more
- pjc50 2y ago
  See the discussion on why sqlite insists on vendoring its build dependencies as far as possible and not using, say, CMake.
- anthk 2y ago
  Guix fixes that in the spot.
chatmasta 2y ago
Here’s the same thing in Poetry (2022): https://www.splitgraph.com/blog/poetry-dependency-resolver-sudoku https://www.splitgraph.com/blog/poetry-dependency-resolver-s...
- teschmitt 2y ago
  Was just about to say: I've seen this before but building it with a universally usable requirements.txt is even cooler.
echoangle 2y ago
> 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. Is that actually sufficient? Can every system that’s solving something that’s NP-complete solve every other NP-complete problem?
- rolisz 2y ago
  Yes, NP complete means that every other NP problem is reducible to it.
- zahlman 2y ago
  >Can every system that’s solving something that’s NP-complete solve every other NP-complete problem? Yes, by definition (https://en.wikipedia.org/wiki/NP-completeness https://en.wikipedia.org/wiki/NP-completeness , point 4).
- arjvik 2y ago
  I think for Sudoku to be NP-Complete, it needs to be generalized to arbitrary board sizes (at the very least)
  - tetha 2y ago
    Correct, if the complexity guys talk about NP-complete sudoku, it's always about solving Sudokus of an arbitrary, but fixed and finite size. The problem class of "Solve an arbitrary Sudoku of Size 9" might even be constant runtime, since it's a finite set to search through.
    - SJC_Hacker 2y ago
      Does the Sudoku size have to be perfect square, or can other sizes exist? I suppose you could leave some blank and make the squares the next largest perfect square
      - tetha 2y ago
mi_lk 2y ago
See also this 2008 post using Debian package system to solve Sudoku: https://web.archive.org/web/20160326062818/http://algebraicthunk.net/~dburrows/blog/entry/package-management-sudoku/ https://web.archive.org/web/20160326062818/http://algebraict...
revskill 2y ago
This is a hack.
- jessekv 2y ago
  And why I come here for... er, news.
worewood 2y ago
This is type of cool hacking I like to see. Kudos! (Or better, Sukodus :) )
alentred 2y ago
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 "special". This one, it has an air of old-school computer magic around it, probably because it is so elegant and simple.
anthk 2y ago
Now, in MicroLisp, Common Lisp and maybe Emacs' Elisp too: http://www.ulisp.com/show?33J9 http://www.ulisp.com/show?33J9

305 points by Yenrabbit 2y ago

niyonx 2y ago

How did you even think of that? Nice!

yochem 2y ago

No way pip actually is a really inefficient SAT solver!

stabbles 2y ago
For a long time it was not because there was no backtracking. Now it is just an exhaustive, recursive search: for the current package try using versions from newest to oldest, enqueue its dependencies, if satisfied return, if conflict continue.
- taeric 2y ago
  If there was no backtracking, that implies it couldn't solve every sudoku? That is rather amusing with the implication that it couldn't solve every dependency, as well?
fernandotakai 2y ago
uv actually talks about this in their resolver docs https://docs.astral.sh/uv/reference/resolver-internals/ https://docs.astral.sh/uv/reference/resolver-internals/

ziofill 2y ago

but how does it know the constraints?

jsnell 2y ago
The constraints are going to be static and independent of the puzzle. So I expect they're encoded in the package dependencies. So for example version 1 of the package sudoku_0_0 will conflict with all of: version 1 of sudoku_[0-8]_0; version 1 of sudoku_0_[0-8]; version 1 of [012]_ [012].
- roywiggins 2y ago
  generate_packages makes it moderately clear: https://github.com/konstin/sudoku-in-python-packaging/blob/main/generate_packages.py https://github.com/konstin/sudoku-in-python-packaging/blob/m...
thangngoc89 2y ago
This is the content of sudoku_0_0-1-py3-none-any.whl. So when the (0,0) cell is 1, none of the cells in the same row, column and subgrid should be 1. Requires-Dist: sudoku_0_1 != 1 Requires-Dist: sudoku_0_2 != 1 Requires-Dist: sudoku_0_3 != 1 Requires-Dist: sudoku_0_4 != 1 Requires-Dist: sudoku_0_5 != 1 Requires-Dist: sudoku_0_6 != 1 Requires-Dist: sudoku_0_7 != 1 Requires-Dist: sudoku_0_8 != 1 Requires-Dist: sudoku_1_0 != 1 Requires-Dist: sudoku_2_0 != 1 Requires-Dist: sudoku_3_0 != 1 Requires-Dist: sudoku_4_0 != 1 Requires-Dist: sudoku_5_0 != 1 Requires-Dist: sudoku_6_0 != 1 Requires-Dist: sudoku_7_0 != 1 Requires-Dist: sudoku_8_0 != 1 Requires-Dist: sudoku_0_1 != 1 Requires-Dist: sudoku_0_2 != 1 Requires-Dist: sudoku_1_0 != 1 Requires-Dist: sudoku_1_1 != 1 Requires-Dist: sudoku_1_2 != 1 Requires-Dist: sudoku_2_0 != 1 Requires-Dist: sudoku_2_1 != 1 Requires-Dist: sudoku_2_2 != 1
IshKebab 2y ago
Yeah they missed out the actual interesting bit from the readme...

simonw 2y ago

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: https://simonwillison.net/2024/Oct/21/sudoku-in-python-packaging/ https://simonwillison.net/2024/Oct/21/sudoku-in-python-packa... 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 "Requires-Dist" rules. I ran a speed comparison too. Using the uv pip resolver it took 0.24s - with the older pip-compile tool it took 17s.

seanw444 2y ago
Wow, uv really is fast.
- jebebeebehhe 2y ago
  As is simonw writing that post in under 60m assuming he first saw the concept here on HN.
  - deleted 2y ago
    [deleted]
  - Medox 2y ago
    Using the simonw resolver is took under 3600s *
  - simonw 2y ago
    Nah I wrote this one a couple of days ago when I first saw the Sudoku solving project on Mastodon.
    - jeanlucas 2y ago
      Thank you, I was going to point out the post on your blog has date of publication lol
c10n3x 2y ago

visarga 2y ago

That'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.

austinjp 2y ago
This describes the day I wasted on Monday before I gave up and wrote some damn deterministic code instead of using some damn AI.
hskalin 2y ago
Sometimes I just change the version of the package in requirements to fit with others and pray that it works out (a few times it does)
nicman23 2y ago
honestly if the ml does not have a docker image - not compose no build an image- i do not even bother any more
pjc50 2y ago
See the discussion on why sqlite insists on vendoring its build dependencies as far as possible and not using, say, CMake.
anthk 2y ago
Guix fixes that in the spot.

chatmasta 2y ago

Here’s the same thing in Poetry (2022): https://www.splitgraph.com/blog/poetry-dependency-resolver-sudoku https://www.splitgraph.com/blog/poetry-dependency-resolver-s...

teschmitt 2y ago
Was just about to say: I've seen this before but building it with a universally usable requirements.txt is even cooler.

echoangle 2y ago

> 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. Is that actually sufficient? Can every system that’s solving something that’s NP-complete solve every other NP-complete problem?

rolisz 2y ago
Yes, NP complete means that every other NP problem is reducible to it.
zahlman 2y ago
>Can every system that’s solving something that’s NP-complete solve every other NP-complete problem? Yes, by definition (https://en.wikipedia.org/wiki/NP-completeness https://en.wikipedia.org/wiki/NP-completeness , point 4).
arjvik 2y ago
I think for Sudoku to be NP-Complete, it needs to be generalized to arbitrary board sizes (at the very least)
- tetha 2y ago
  Correct, if the complexity guys talk about NP-complete sudoku, it's always about solving Sudokus of an arbitrary, but fixed and finite size. The problem class of "Solve an arbitrary Sudoku of Size 9" might even be constant runtime, since it's a finite set to search through.
  - SJC_Hacker 2y ago
    Does the Sudoku size have to be perfect square, or can other sizes exist? I suppose you could leave some blank and make the squares the next largest perfect square
    - tetha 2y ago

mi_lk 2y ago

See also this 2008 post using Debian package system to solve Sudoku: https://web.archive.org/web/20160326062818/http://algebraicthunk.net/~dburrows/blog/entry/package-management-sudoku/ https://web.archive.org/web/20160326062818/http://algebraict...

revskill 2y ago

This is a hack.

jessekv 2y ago
And why I come here for... er, news.

worewood 2y ago

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

alentred 2y ago

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 "special". This one, it has an air of old-school computer magic around it, probably because it is so elegant and simple.

anthk 2y ago

Now, in MicroLisp, Common Lisp and maybe Emacs' Elisp too: http://www.ulisp.com/show?33J9 http://www.ulisp.com/show?33J9