Solving the NYTimes Pips puzzle with a constraint solver(righto.com)
righto.com
Solving the NYTimes Pips puzzle with a constraint solver
https://www.righto.com/2025/10/solve-nyt-pips-with-constraints.html
7 comments
Author here if anyone has questions. I was inspired to look at constraint solvers by the recent HN discussion "Many hard LeetCode problems are easy constraint problems" https://news.ycombinator.com/item?id=45222695
I too have a solver, but it is the dumb kind, with the only real optimization being the one you described:
> An easy optimization is to check the constraints after each domino is added. For instance, as soon as the "less than 5" constraint is violated, you can backtrack and skip that entire section of the tree. In this way, only a subset of the tree needs to be searched; the number of branches will be large, but hopefully manageable
The solve function simply finds the first unoccupied square, then for each unoccupied neighbor of that square and each unused tile it places that tile on those two squares, checks the constraint groups those squares belong to to see if this placement violates them, and if not calls itself recursively. When that call returns if the tile is not symmetric it flips the orientation, checks constraints, and recurses.
If when called it cannot find an unoccupied square that means the level above actually solved the puzzle so it records the solution.
So far there has only been one puzzle where this was really slow, 2025-10-17 hard, which had 16 tiles. On my M2 Max Mac Studio it took 37 minutes. Every other puzzle I've given it has taken at most a few seconds, including hard 2025-10-09 which was also a 16 tile puzzle. That one was 7 seconds.
My guess is that if I changed the way the solve functions picks the square to start with it could greatly change the time. Right now it just takes the first open square found scanning right to left and top to bottom. Maybe something like giving priority to squares in small constraint groups would be more effective.
I'm not fully sure mine is correct. The code is simple enough that I can't see how it could be missing solutions...but on that one you said has 384 solutions mine only finds 344.
> An easy optimization is to check the constraints after each domino is added. For instance, as soon as the "less than 5" constraint is violated, you can backtrack and skip that entire section of the tree. In this way, only a subset of the tree needs to be searched; the number of branches will be large, but hopefully manageable
The solve function simply finds the first unoccupied square, then for each unoccupied neighbor of that square and each unused tile it places that tile on those two squares, checks the constraint groups those squares belong to to see if this placement violates them, and if not calls itself recursively. When that call returns if the tile is not symmetric it flips the orientation, checks constraints, and recurses.
If when called it cannot find an unoccupied square that means the level above actually solved the puzzle so it records the solution.
So far there has only been one puzzle where this was really slow, 2025-10-17 hard, which had 16 tiles. On my M2 Max Mac Studio it took 37 minutes. Every other puzzle I've given it has taken at most a few seconds, including hard 2025-10-09 which was also a 16 tile puzzle. That one was 7 seconds.
My guess is that if I changed the way the solve functions picks the square to start with it could greatly change the time. Right now it just takes the first open square found scanning right to left and top to bottom. Maybe something like giving priority to squares in small constraint groups would be more effective.
I'm not fully sure mine is correct. The code is simple enough that I can't see how it could be missing solutions...but on that one you said has 384 solutions mine only finds 344.
> My guess is that if I changed the way the solve functions picks the square to start with it could greatly change the time. Right now it just takes the first open square found scanning right to left and top to bottom. Maybe something like giving priority to squares in small constraint groups would be more effective.
Your guess is correct. Take a look at my backtracking solver linked from another comment; one of the optimizations I added after the fact was to select a square with the "smallest" constraint for the next placement, with the motivation of avoiding a rathole. (The 2025-09-15 puzzle with the =63 constraint is a good test case, FWIW.)
My Rust solver running on an M3 Max Macbook Pro is often under a second and never more than about 30 seconds. (I did pull down all of the past puzzles using an observation from Evan Matthews in his solver: https://github.com/ematth/pips)
Your guess is correct. Take a look at my backtracking solver linked from another comment; one of the optimizations I added after the fact was to select a square with the "smallest" constraint for the next placement, with the motivation of avoiding a rathole. (The 2025-09-15 puzzle with the =63 constraint is a good test case, FWIW.)
My Rust solver running on an M3 Max Macbook Pro is often under a second and never more than about 30 seconds. (I did pull down all of the past puzzles using an observation from Evan Matthews in his solver: https://github.com/ematth/pips)
So much fun. I'm not sure if the game is more fun or writing a solver for the game is more fun... Here's my entry written in Rust from a spec in Markdown — executed as an initial AI coding experiment with Gemini, Claude, and Codex working individually and then assessing each other's work:
https://github.com/prb/pips-solver/blob/main/README.md
https://github.com/prb/pips-solver/blob/main/README.md
This is excellent. I play each day, and I started to wonder if the puzzles had multiple solutions. I wouldn’t have guessed 384 solutions however!
The hard one for 2025-09-15 had millions of solutions. Here's that puzzle, in a text format that I use to enter puzzles for my solver.
The second part is the constraint groups. The format is simply the letter assigned to that constraint group and then the constraint. The possible constraints are N, <N, >N, =, and <>, meaning that the group must sum to N, sum to <N, sum to >N, contain the same number of pips in each square, and contain no two squares with the same number of pips, respectively.
The final part is the available tiles, each represented by two digits showing the number of pips on the two squares of the tile.
There are some tiles that must go in fixed positions for this one. Square D must have a 6, and we only have one tile with a 6 so that most go there, and D only has one neighbor so there is only one way to place it.
Squares C and E are adjacent and must each be 0. We only have two 0's and the are on the same tile, so that one must go on C and E. B and H each must have a 1, and we only have two ones, the 12 and 15 tile. Which goes where? We can figure that out by noting that whichever is used on H will have its other end on the "-" square, which is the only square not part of a constraint group. To satisfy all the constraint groups we need a total of 79 pips. The total number of pips on the tiles is 81. We can only afford to lose 2 to that "-" square, and so H gets the 12 tile.
The 1 of the 15 then has to go on B, and no matter how we orient it the 5 will be in the A group.
F and G are constrained to 4 each, and we have 4's available on the 42 43 44 and 45 tiles.
Even with some of the previously forced tile placements taking filling some of the squares in the big A group, and no matter how we cover F and G (which can also cover up to 2 squares in the A group), we are still going to end up with several leftover tiles and several several empty A squares that they have to fill with no constraints on how they have to go into the A group, and so we get a large number of combinations that work.
My solver says there are a total of 2 764 800. I've tried to verify that by working out all the combinations manually but I'm getting different answers depending on how I do it, so I'm missing some case I think.
Today's (2025-10-18) hard,
..AAB
.AAAAAA
.ACAAAA
DAEAFGA-H
A 63
B 1
C 0
D 6
E 0
F 4
G 4
H 1
65 12 45 15
53 25 44 00
42 33 34 55
The second part is the constraint groups. The format is simply the letter assigned to that constraint group and then the constraint. The possible constraints are N, <N, >N, =, and <>, meaning that the group must sum to N, sum to <N, sum to >N, contain the same number of pips in each square, and contain no two squares with the same number of pips, respectively.
The final part is the available tiles, each represented by two digits showing the number of pips on the two squares of the tile.
There are some tiles that must go in fixed positions for this one. Square D must have a 6, and we only have one tile with a 6 so that most go there, and D only has one neighbor so there is only one way to place it.
Squares C and E are adjacent and must each be 0. We only have two 0's and the are on the same tile, so that one must go on C and E. B and H each must have a 1, and we only have two ones, the 12 and 15 tile. Which goes where? We can figure that out by noting that whichever is used on H will have its other end on the "-" square, which is the only square not part of a constraint group. To satisfy all the constraint groups we need a total of 79 pips. The total number of pips on the tiles is 81. We can only afford to lose 2 to that "-" square, and so H gets the 12 tile.
The 1 of the 15 then has to go on B, and no matter how we orient it the 5 will be in the A group.
F and G are constrained to 4 each, and we have 4's available on the 42 43 44 and 45 tiles.
Even with some of the previously forced tile placements taking filling some of the squares in the big A group, and no matter how we cover F and G (which can also cover up to 2 squares in the A group), we are still going to end up with several leftover tiles and several several empty A squares that they have to fill with no constraints on how they have to go into the A group, and so we get a large number of combinations that work.
My solver says there are a total of 2 764 800. I've tried to verify that by working out all the combinations manually but I'm getting different answers depending on how I do it, so I'm missing some case I think.
Today's (2025-10-18) hard,
..AA
..AA
BBACCC
.DACC
..EEF
..-GGG
.....-
....HH
A <>
B 8
C 29
D 0
E 3
F >3
G 7
H =
41 10 16 06
66 62 64 56
44 25 42 05
Just for grins, I ran stats on most (but not all of the puzzles):
• Solution Counts Overview
• Solution Counts Overview
- Processed all 183 stored puzzles (61 dates × 3 difficulties) via target/
release/count_solutions, saving raw results to gpt_5_codex/output/
solution_counts.csv.
- 131 puzzles (≈72%) have exactly one solution: easy 50, medium 44, hard 37.
- Remaining puzzles show small clusters of alternatives except for a handful of
hard cases with large branching factors.
Most Multi-Solution Puzzles
- 2025-09-15 hard: 2,764,800 solutions
- 2025-10-05 hard: 344 solutions
- 2025-09-30 hard: 110 solutions
- 2025-09-04 hard: 86 solutions
- 2025-08-23 hard: 80 solutions