Solving the NYTimes Pips puzzle with a constraint solver

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.

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.

  ..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 first part shows the layout, with each line representing one row. Each square of the puzzle is assigned a letter or '-'. All squares with the same letter are part of the same constraint group. Squares that are not constrained get '-'. The rows are aligned so the each square is in the same column as any square adjacent to it in the previous or next row. Dots are used to pad shorter rows on the left for alignment. Dots are also used if there is an skipped space in a row.

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

has 10 464 solutions. Like the earlier example some of these are trivial rearrangements within areas, but they fall into several families that have non-trivial differences between the families.