Grappling with Infinity in Constraint Solvers
Published on: 2025-04-28 03:02:15
Grappling with infinity in constraint solvers
Published November 17, 2019 by Chris Patuzzo
In 2016, I created a programming language called Sentient. Since then, I’ve had time to reflect and think about the language. This series is about that.
Many constraint-satisfaction problems deal with infinity in some shape or form. Even rudimentary problems, like "Find two integers that sum to 10". Solutions include:
(4, 6)
(-7, 17)
(-1953856112, 1953856122)
That (d)escalated quickly!
In fact, there are infinitely many solutions and infinitely many pairs of integers to test. Here’s a Sentient program to solve this problem:
int a, b ; invariant a + b == 10 ; expose a, b ; ▲ A Sentient program to find integers that sum to 10
This article is about Sentient, but many of the concepts apply to constraint solvers in general.
We can run this with the --number 0 option, to continuously find solutions:
▲ Finding multiple solutions with Sentient
When Sentient returns {} , it has exhausted the
... Read full article.