Optimizing Solving NYT's Pips Game

*this is an ongoing writeup - I'll probably finish up the solver in a week or so

A few days ago, one of my co-TAs introduced me to the New York Times' Pips game. For those who haven't played, the main goal is to tile dominos across a grid with certain constraints:

• = - all squares in a region marked with this have to contain the same value
• ≥/≤ - all squares in a region marked with this have to conform to the inequality
• [0..9]* - all squares in a region marked with this have to sum to the given value

Here's a small snippet of today's Easy board:

Here's a small snippet of today's Easy board:

Honestly on first look, using a naive backtracking algorithm definitely has a bunch of low hanging fruit:

• Dominoes, being 2x1, can only be placed in a few orientations - we can't have off-by-one errors or leave any squares blank.

• Also, orientation for duplicate dominoes doesn't matter either - we can prune cases where a (3 | 3) domino switches, for example
• We can definitely prune out impossible states early - for example, if a region's sum constraint cannot be satisfied with the remaining dominoes.