| CARVIEW |
Select Language
HTTP/2 200
date: Sat, 11 Oct 2025 05:56:45 GMT
content-type: text/html; charset=utf-8
server: cloudflare
access-control-allow-origin: *
cache-control: public, max-age=0, must-revalidate
content-disposition: inline
report-to: {"group":"cf-nel","max_age":604800,"endpoints":[{"url":"https://a.nel.cloudflare.com/report/v4?s=1zSw9FTuGKXu2%2Fd2eVDWK4iiJzdbeBHkLskmhNAhq%2FyE0SZzMwlNs0Kbo4KEG5qBXbzI69LKpuHN26SDHarwKlBuTiiNQdWoCuK1B4yC5uOV2Q%3D%3D"}]}
x-matched-path: /blog/poetry-dependency-resolver-sudoku
x-vercel-cache: HIT
x-vercel-id: fra1::nk4v5-1760162204606-1f39d9f1a21b
vary: Accept-Encoding
x-varnish: 4718635
age: 317475
via: 1.1 varnish (Varnish/6.5)
x-cache: MISS
nel: {"report_to":"cf-nel","success_fraction":0.0,"max_age":604800}
strict-transport-security: max-age=63072000
cf-cache-status: DYNAMIC
content-encoding: gzip
cf-ray: 98cc1db1ad2f0b19-BOM
alt-svc: h3=":443"; ma=86400
Solving Sudoku with Poetry's dependency resolver | Splitgraph 
Splitgraph has been acquired by EDB! Read the blog post.
Jun 8, 2022 · By Artjoms Iškovs
READING TIME: 9 min
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.
Oct 24, 2023 ·By Artjoms Iškovs, Miles Richardson
1 min readEDB acquires Splitgraph
Splitgraph is joining EDB, the leader in accelerating Postgres in the enterprise.
Aug 30, 2023 ·By Peter Neumark
15 min readHow we built a ChatGPT plugin for Splitgraph
We built a ChatGPT plugin for querying Splitgraph without writing SQL. Along the way, we discovered a better way to write LLM-powered applications.
Aug 24, 2023 ·By Patrick Skinner
3 min readWriting UDFs in Golang
We return to the wide world of WASM. In our previous round we implemented a UDF using Rust; today we're porting it to Golang.
Aug 9, 2023 ·By Grzegorz Rozdzialik
11 min readParsing pgSQL with tree-sitter in WASM
We used tree-sitter to show the tables referenced in the query inside the Splitgraph Console.
Jun 19, 2023 ·By Grzegorz Rozdzialik
14 min readKeeping Apollo Cache up-to-date after mutations
A discussion of approaches to keep Apollo cache consistent with the API data after invoking GraphQL mutations.
Jun 14, 2023 ·By Peter Neumark
6 min readBuilding a GPT-powered agent to answer questions using data from Splitgraph
Follow along as we build a GPT-powered bot capable of answering natural language questions by finding relevant Splitgraph repositories and querying them via automatically generated SQL.
May 24, 2023 ·By Patrick Skinner
9 min readDeploying a serverless Seafowl DB to Google Cloud Run using GCS FUSE and SQLite
Learn how to combine Seafowl with GCS FUSE to achieve true scale to zero. Serve users at the edge with a web (HTTP)-first analytical database that works on GCP Cloud Run, including within the "always free" tier.
May 22, 2023 ·By Peter Neumark
5 min readUsing Dagster with Seafowl
Import the result of your data pipeline into Seafowl easily using Dagster!
Apr 12, 2023 ·By Peter Neumark
3 min readSQLite file uploads
Importing SQLite data into Splitgraph is now as easy as drag-n-drop!
Apr 11, 2023 ·By Marko Grujić
14 min readA Lakehouse by the sea: Migrating Seafowl storage layer to delta-rs
Announcing the replacement of our custom storage layer with Delta Lake, facilitated by its open-source Rust implementation.
Jan 12, 2023 ·By Patrick Skinner
6 min readOpen Data Monitor
How can we track open government datasets over time? Say hello to Open Data Monitor, a Socrata tracking tool powered by Seafowl and Splitgraph.
Dec 14, 2022 ·By Marko Grujić
12 min readRust visitor pattern and efficient DataFusion query federation
We explore the inner workings of DataFusion filter pushdown optimisation, and see what it takes to ship them to remote data sources.
Dec 9, 2022 ·By Peter Neumark
9 min readDeciding if I'm urban with WebAssembly and Seafowl
I used Seafowl to analyze how much of a city slicker I am—with geographic user-defined WASM functions and caffeine addiction!
Nov 29, 2022 ·By Peter Neumark
8 min readExtending Seafowl with WebAssembly
How can Seafowl users extend the database's builtin capabilities in a safe, portable and efficient way? The answer is WebAssembly, read on to learn how!
Nov 18, 2022 ·By Marko Grujić
10 min readTable partitioning and time travel queries: Seafowl case study
We discuss how Seafowl performs table partitioning to enable efficient versioning and time travel queries
Oct 12, 2022 ·By Artjoms Iškovs
12 min read(Ab)using CDNs for SQL queries
A deep dive into how we designed Seafowl's REST API to be HTTP cache and CDN friendly, including some discussion of ETags and other HTTP cache mechanics.
Oct 9, 2022 ·By Artjoms Iškovs
6 min readSeafowl: a database for analytics at the edge
Our new project: a CDN-friendly analytical database that's up to 10x faster than PostgreSQL and up to 5x faster than Splitgraph.
Aug 17, 2022 ·By Patrick Skinner
4 min readSELECT directly from the browser
How Splitgraph's DDN HTTP API lets you run SQL queries directly from the browser, opening new possiblities for client-side data-driven apps.
Jul 6, 2022 ·By Patrick Skinner
6 min readBuilding a data-driven app with Splitgraph and Streamlit
We demonstrate how combining Splitgraph and Streamlit lets devs and data scientists more easily build data-driven apps. In this example we plot NYC subway turnstile data to try and glean how NYC's Covid recovery is going.
Jun 8, 2022 ·By Artjoms Iškovs
9 min readSolving Sudoku with Poetry's dependency resolver
An unexpected use case for one of Python's most popular package managers.
May 4, 2022 ·By Artjoms Iškovs
9 min readsplitgraph.yml: Terraform for your data stack
We showcase the
splitgraph.yml format, which lets you programmatically manage your datasets on Splitgraph, change their data source settings and define dbt transformations.Apr 28, 2022 ·By Peter Neumark
1 min readPlanning a vacation with Splitgraph and Observable
Query public Splitgraph repositories from Observable notebooks, by importing the Splitgraph Observable Client to send SQL queries over HTTP to the Splitgraph Data Delivery Network (DDN).
Apr 14, 2022 ·By Peter Neumark
2 min readGet your own private Splitgraph data portal
Deploy a demo instance of a Dedicated Data Portal, so you can experiment with Splitgraph features in a single-tenant environment. Try it today, free for 7 days, no credit card required.
Mar 7, 2022 ·By Peter Neumark
10 min readCombining multiple GraphQL backends with schema stitching
Read about we use GraphQL schema stitching to provide a single coherent schema for accessing several services with shared types from overlapping GraphQL schemas.
Feb 14, 2022 ·By Marko Grujić
10 min readPostgreSQL FDW aggregation pushdown part III: Elasticsearch edition
We continue our series on aggregation pushdown and turn our attention to our Elasticsearch FDW. Implementation details, performance considerations as well as a few Postgres tidbits are shared.
Feb 9, 2022 ·By Marko Grujić
9 min readPostgreSQL FDW aggregation pushdown part II: Snowflake speedup
We demonstrate a concrete application of aggregation pushdown mechanism in the form of our Snowflake FDW. Actual performance benefits are quantified for a selection of real-life examples.
Feb 8, 2022 ·By Artjoms Iškovs
3 min readShare datasets like Notion pages
Splitgraph now supports advanced data sharing settings. Make a repository private, invite a collaborator and control their level of access, all from a simple Web UI.
Feb 4, 2022 ·By Marko Grujić
15 min readPostgreSQL FDW aggregation pushdown part I: modifying Multicorn
We recently implemented support for aggregation and grouping pushdown in the Multicorn FDW. In this post, we'll demonstrate it on a simple toy example and discuss how PostgreSQL aggregation pushdown works in general.
Feb 3, 2022 ·By Artjoms Iškovs
10 min readScheduling, versioning and cataloging: introducing our dbt integration
We showcase the ability to run dbt models on Splitgraph, triggering them on a schedule as well as using GitHub Actions. We also talk about how it works and share more plans for our dbt integration.
Feb 2, 2022 ·By Miles Richardson
3 min readDrag, drop and share CSV files as queryable SQL tables
You can now upload CSV files to Splitgraph from the web, so that you can query them with SQL by pointing your Postgres client to the Data Delivery Network (DDN). Share data publicly or with only those you invite – all discoverable and queryable from a single unified interface.
Dec 23, 2021 ·By Artjoms Iškovs
7 min readAirbyte, dbt, Splitgraph: how we built our modern data stack
We talk about our modernized data stack that uses Airbyte for data ingestion, dbt for transformations and Splitgraph itself for storage, versioning, discoverability and querying.
Dec 20, 2021 ·By Marko Grujić
5 min readPreview Environments: Spinning up temporary Splitgraph instances from any commit
We talk about how we use GitLab's review apps functionality to preview and test Splitgraph Cloud deployments.
Sep 18, 2020 ·By Artjoms Iškovs
10 min readDogfooding Splitgraph for cross-database analytics in Metabase
We talk about how we use Metabase, Splitgraph and PostgreSQL foreign data wrappers to build BI dashboards that are backed by federated queries across our Matomo and Elasticsearch instances.
Aug 19, 2020 ·By Artjoms Iškovs, Miles Richardson
7 min readPort 5432 is open: introducing the Splitgraph Data Delivery Network
We launch the Splitgraph Data Delivery Network: a single endpoint that lets any PostgreSQL application, client or BI tool to connect and query over 40,000 public datasets hosted or proxied by Splitgraph.
Jul 28, 2020 ·By Artjoms Iškovs
8 min readSplitgraph infrastructure, part 3: Using Docker Compose in production
We finish our overview of Splitgraph's infrastructure by talking about why and how we use Docker Compose to run the Splitgraph registry in production.
Jul 14, 2020 ·By Artjoms Iškovs
13 min readSupercharging dbt with Splitgraph: versioning, sharing, cross-DB joins
We discuss how you can use Splitgraph with dbt to add versioning and cross-database joins to dbt models. We also show how to use dbt to reference Splitgraph datasets, including through a purpose-built Splitgraph adapter.
Jul 13, 2020 ·By Artjoms Iškovs
6 min readThrowing away the backend: Towards a data delivery network
We discuss the trends of serverless and edge computing, talk about why our SQL server is open to the public and propose the idea of a data delivery network.
Jul 8, 2020 ·By Miles Richardson
7 min readQuerying 40,000+ datasets with SQL
Learn about how Splitgraph indexes over 40,000 datasets from government and public sources using the Socrata API, Splitgraph mounting, and PostgreSQL foreign data wrappers.
Jul 8, 2020 ·By Artjoms Iškovs
7 min readSplitgraph infrastructure, part 2: Integration testing with Docker Compose
We continue our overview of Splitgraph's internal build infrastructure by talking about how we run end-to-end integration tests. We also discuss using Jinja to generate configuration and inject secrets into our components.
Jul 6, 2020 ·By Artjoms Iškovs
8 min readSplitgraph infrastructure, part 1: Using Make to build multiple Docker images efficiently
We begin our overview of Splitgraph's internal build infrastructure by discussing how we build Docker images in development and CI using Make and Docker BuildKit.
Jul 2, 2020 ·By Artjoms Iškovs
9 min readForeign data wrappers: PostgreSQL's secret weapon?
We talk about foreign data wrappers, a PostgreSQL feature that lets you query remote databases directly from your PostgreSQL instance. We also demonstrate how to integrate them with Splitgraph.
Jun 30, 2020 ·By Artjoms Iškovs
5 min readTreat your datasets like cattle, not pets
We talk about the "pets versus cattle" idea in software and discuss how Splitgraph helps to apply it to data science and data engineering.
Jun 26, 2020 ·By Artjoms Iškovs
6 min readIt took 10 minutes to add support for DataGrip to Splitgraph
We discuss a philosophy of not breaking existing abstractions that we think explains the success of tools like Docker and Git and how we applied it to Splitgraph, helping us launch with multiple integrations.
Jun 24, 2020 ·By Miles Richardson, Artjoms Iškovs
6 min readWelcome to Splitgraph
Announcing Splitgraph, a data versioning and management system that allows you to work with data like you work with code.
Splitgraph
Splitgraph Inc, registered in Delaware, USA
Splitgraph Limited, registered in England and Wales No. 11657324
Made with
on four continents.