Splitgraph has been acquired by EDB! Read the blog post.
Solving Sudoku with Poetry's dependency resolver
An unexpected use case for one of Python's most popular package managers.
While waiting for/sitting on various types of transportation during the recent spike in demand for travel, I killed time by solving Sudoku puzzles.
A Sudoku puzzle has a simple premise. A 9✕9 grid (split into 3✕3 squares) has to be filled with numbers from 1 to 9 such that each column, row and square only contains one of each digit.
After solving about a dozen boards, I had an idea. Sudoku is a classic constraint satisfaction problem. Solving it with a computer has been done many times before, including with something as unorthodox as SQL (please don't run this on Splitgraph).
I had a more disgusting method in mind.
Package managers like Yarn/Poetry/Cargo do version range and conflict resolution when generating a lockfile. In essence, they are designed for solving constraint satisfaction problems.
So, is it possible to get a dependency resolver to solve Sudoku for me?
Turns out, it is. I put the code up on GitHub and what follows is the explanation of how it works. This is using Poetry, a package and dependency manager for Python projects.
Encoding the board constraints
First, we need to encode the rules of Sudoku in such a way that a dependency resolver can understand them.
We can represent each Sudoku board cell as a Python package with the name
sudoku-cell{row}{col}. Each package has 9 versions {value}.0.0,
corresponding to the value of that cell. Since in Python, a resolved dependency
tree only has one version of each package, this means that every cell can only
have one value, which is what we're after.
In addition, every package also has dependencies on other "cell" packages, with version constraints encoding which values those "cells" can have.
For example, version 3.0.0 of the sudoku-cell25 package represents an
assertion that the cell at row 2, column 5 of the board has the number 3 in it.
The pyproject.toml for this package has a list of all "cell" packages in the
same row, column or a 3x3 square as this cell:
[tool.poetry.dependencies]
python = "^3.6"
sudoku-cell14 = "!= 3.0.0"
sudoku-cell15 = "!= 3.0.0"
sudoku-cell16 = "!= 3.0.0"
sudoku-cell21 = "!= 3.0.0"
sudoku-cell22 = "!= 3.0.0"
sudoku-cell23 = "!= 3.0.0"
sudoku-cell24 = "!= 3.0.0"
sudoku-cell26 = "!= 3.0.0"
sudoku-cell27 = "!= 3.0.0"
sudoku-cell28 = "!= 3.0.0"
sudoku-cell29 = "!= 3.0.0"
sudoku-cell34 = "!= 3.0.0"
sudoku-cell35 = "!= 3.0.0"
sudoku-cell36 = "!= 3.0.0"
sudoku-cell45 = "!= 3.0.0"
sudoku-cell55 = "!= 3.0.0"
sudoku-cell65 = "!= 3.0.0"
sudoku-cell75 = "!= 3.0.0"
sudoku-cell85 = "!= 3.0.0"
sudoku-cell95 = "!= 3.0.0"
To use this version of the package ("put 3 in this cell"), we can't use the same version of any of the conflicting packages ("can't put 3 in cells in the same row, column or square").
I then set up a devpi instance and uploaded all 9✕9✕9 = 729 package versions to it. Theoretically, one could upload them to the public PyPI (these rules are only ever uploaded once, not every time we need to solve a board), but that feels abusive.
Encoding the problem
Now, we can represent an unsolved Sudoku board as another Poetry package:
[tool.poetry.dependencies]
python = "^3.6"
sudoku-cell11 = "*"
sudoku-cell12 = "2.0.0"
sudoku-cell13 = "*"
sudoku-cell14 = "8.0.0"
sudoku-cell15 = "*"
sudoku-cell16 = "9.0.0"
sudoku-cell17 = "*"
sudoku-cell18 = "*"
sudoku-cell19 = "*"
sudoku-cell21 = "3.0.0"
sudoku-cell22 = "7.0.0"
sudoku-cell23 = "*"
sudoku-cell24 = "6.0.0"
...
This pyproject.toml depends on all 81 "cell" packages, pinning known cells to
their values.
Solving the problem
We can now solve the problem by simply running poetry update --lock. In order
to generate a lockfile for this package, Poetry has to find a version (value)
for each of the 81 packages (cells) in such a way that they don't conflict with
each other. Since we encoded the rules of Sudoku as inter-package dependencies,
the lockfile will contain a solution to this Sudoku board.
Running poetry update with -vvv even outputs the internal assertions Poetry
is deriving about the constraints:
125: conflict: sudoku-cell52 (3.0.0) depends on sudoku-cell55 (!=3.0.0)
125: ! sudoku-cell52 (3.0.0) is partially satisfied by not sudoku-cell52 (5.0.0)
125: ! which is caused by "sudoku-cell52 (5.0.0) depends on sudoku-cell51 (!=5.0.0)"
125: ! thus: sudoku-cell52 (3.0.0 || 5.0.0) requires sudoku-cell55 (!=3.0.0) or sudoku-cell51 (!=5.0.0)
125: ! not sudoku-cell51 (!=5.0.0) is partially satisfied by sudoku-cell51 (!=8.0.0)
125: ! which is caused by "sudoku-cell11 (8.0.0) depends on sudoku-cell51 (!=8.0.0)"
125: ! thus: if sudoku-cell52 (3.0.0 || 5.0.0) and sudoku-cell11 (8.0.0) then sudoku-cell55 (!=3.0.0) or sudoku-cell51 (<5.0.0 || >5.0.0,<8.0.0 || >8.0.0)
...
131: selecting sudoku-cell14 (6.0.0)
131: Version solving took 269.771 seconds.
131: Tried 131 solutions.
Success
Finally, we can parse the lockfile (read which version of each package Poetry has chosen) and emit it as a solved Sudoku board:
ORIGINAL SOLUTION
. . . | 6 4 1 | 9 . 5 3 2 8 | 6 4 1 | 9 7 5
. . . | . . 9 | 4 . . 1 6 5 | 8 7 9 | 4 3 2
. . 7 | 2 . . | . . . 9 4 7 | 2 3 5 | 1 6 8
-------|-------|------- -----------------------
2 . . | . 5 . | . . . 2 7 4 | 1 5 6 | 8 9 3
. . 1 | . . 7 | 6 . 4 8 5 1 | 3 9 7 | 6 2 4
. 9 . | . . . | 5 . 7 6 9 3 | 4 8 2 | 5 1 7
-------|-------|------- -----------------------
. 8 . | . . . | . . . 4 8 9 | 7 6 3 | 2 5 1
. . 2 | . . . | . 8 6 5 3 2 | 9 1 4 | 7 8 6
. . 6 | 5 2 . | . . . 7 1 6 | 5 2 8 | 3 4 9
Failed attempt: Yarn
In the beginning, I tried a similar idea with Yarn, with package.json files
for each individual "cell" package encoding dependencies on other packages:
{
"name":"sudoku-cell26",
"version":"6.0.0",
"main":"index.js",
"license":"MIT",
"dependencies":{
"sudoku-cell14":"1.0.0 || 2.0.0 || 3.0.0 || 4.0.0 || 5.0.0 || 7.0.0 || 8.0.0 || 9.0.0",
"sudoku-cell15":"1.0.0 || 2.0.0 || 3.0.0 || 4.0.0 || 5.0.0 || 7.0.0 || 8.0.0 || 9.0.0",
"sudoku-cell16":"1.0.0 || 2.0.0 || 3.0.0 || 4.0.0 || 5.0.0 || 7.0.0 || 8.0.0 || 9.0.0",
...
However, Yarn resolved dependencies using multiple versions for some packages:
# This file is generated by running "yarn install" inside your project.
# Manual changes might be lost - proceed with caution!
__metadata:
version: 6
cacheKey: 8
? "sudoku-cell11@npm:*, sudoku-cell11@npm:1.0.0 || 2.0.0 || 3.0.0 || 4.0.0 ||
5.0.0 || 6.0.0 || 7.0.0 || 9.0.0, sudoku-cell11@npm:1.0.0 || 2.0.0 || 3.0.0 ||
4.0.0 || 5.0.0 || 6.0.0 || 8.0.0 || 9.0.0, sudoku-cell11@npm:1.0.0 || 2.0.0 ||
3.0.0 || 4.0.0 || 5.0.0 || 7.0.0 || 8.0.0 || 9.0.0, sudoku-cell11@npm:1.0.0 ||
2.0.0 || 3.0.0 || 4.0.0 || 6.0.0 || 7.0.0 || 8.0.0 || 9.0.0,
sudoku-cell11@npm:1.0.0 || 2.0.0 || 3.0.0 || 5.0.0 || 6.0.0 || 7.0.0 || 8.0.0
|| 9.0.0, sudoku-cell11@npm:1.0.0 || 3.0.0 || 4.0.0 || 5.0.0 || 6.0.0 || 7.0.0
|| 8.0.0 || 9.0.0, sudoku-cell11@npm:2.0.0 || 3.0.0 || 4.0.0 || 5.0.0 || 6.0.0
|| 7.0.0 || 8.0.0 || 9.0.0"
: version: 9.0.0
resolution: "sudoku-cell11@npm:9.0.0"
dependencies:
sudoku-cell12:
1.0.0 || 2.0.0 || 3.0.0 || 4.0.0 || 5.0.0 || 6.0.0 || 7.0.0 || 8.0.0
sudoku-cell13:
1.0.0 || 2.0.0 || 3.0.0 || 4.0.0 || 5.0.0 || 6.0.0 || 7.0.0 || 8.0.0
---
? "sudoku-cell11@npm:1.0.0 || 2.0.0 || 3.0.0 || 4.0.0 || 5.0.0 || 6.0.0 || 7.0.0
|| 8.0.0"
: version: 8.0.0
resolution: "sudoku-cell11@npm:8.0.0"
dependencies:
sudoku-cell12:
1.0.0 || 2.0.0 || 3.0.0 || 4.0.0 || 5.0.0 || 6.0.0 || 7.0.0 || 9.0.0
sudoku-cell13:
1.0.0 || 2.0.0 || 3.0.0 || 4.0.0 || 5.0.0 || 6.0.0 || 7.0.0 || 9.0.0
---
? "sudoku-cell12@npm:*, sudoku-cell12@npm:1.0.0 || 2.0.0 || 3.0.0 || 4.0.0 ||
5.0.0 || 6.0.0 || 7.0.0 || 9.0.0, sudoku-cell12@npm:1.0.0 || 2.0.0 || 3.0.0 ||
4.0.0 || 5.0.0 || 6.0.0 || 8.0.0 || 9.0.0, sudoku-cell12@npm:1.0.0 || 2.0.0 ||
3.0.0 || 4.0.0 || 5.0.0 || 7.0.0 || 8.0.0 || 9.0.0, sudoku-cell12@npm:1.0.0 ||
2.0.0 || 3.0.0 || 4.0.0 || 6.0.0 || 7.0.0 || 8.0.0 || 9.0.0,
sudoku-cell12@npm:1.0.0 || 2.0.0 || 3.0.0 || 5.0.0 || 6.0.0 || 7.0.0 || 8.0.0
|| 9.0.0, sudoku-cell12@npm:2.0.0 || 3.0.0 || 4.0.0 || 5.0.0 || 6.0.0 || 7.0.0
|| 8.0.0 || 9.0.0"
I tried running yarn dedupe which is supposed to deduplicate overlapping
version ranges in the lockfile, but it ran out of memory and crashed. Yarn also
comes with a constraints system, but that's just Prolog so it felt like
cheating.
Conclusion and future work
The code I used to generate the packages and upload them to devpi is on GitHub. You can install it with Poetry and run this experiment locally, for better or for worse.
As for what else can be done with this, I was thinking of using something faster than devpi to feed packages to Poetry (the package upload step takes about 10 minutes and the actual solving process takes a couple of minutes). Maybe it's possible to transpile a Prolog program into a set of Poetry packages. The sky's the limit.
Splitgraph
Made with
on four continents.