Solving the NY Times "Pips" game with F#

6 months ago

Pips is a puzzle game from the New York Times where players cover a shape with dominoes under specific constraints.
The game uses a backtracking algorithm to solve puzzles efficiently, considering geometric tilings and pruning dead ends.
Constraints include equal regions (same pip counts), unequal regions (different pip counts), and sum regions (specific pip totals).
The algorithm checks constraints aggressively during the search to reduce computation time.
F# is used for implementation due to its functional programming strengths and efficiency with .NET.
Performance data shows solving times for various puzzles, with the hardest taking over a second and some having thousands of solutions.
Key data structures include Domino, Cell, Edge, Board, Region, and Puzzle types to model the game state.
The solver uses tiling trees to guide domino placement and checks validity at each step to ensure constraints are met.

Hasty Briefsbeta