Previous Post
splitgraph.yml: Terraform for your data stack

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.