NYT Pips Solver

Solve New York Times Pips puzzles with backtracking

About Pips Puzzles

Pips is a logic puzzle from the New York Times where you must place dominoes on a grid while satisfying various constraints. Each domino has two halves with pips (dots) numbered 0-6, and regions on the board may require specific sums, equal values, or other relationships.

Important: Unlike traditional dominoes, touching domino halves don't need to match—only the region rules apply. Boards can also be non-rectangular with irregular shapes and holes.

The Backtracking Algorithm

Our solver uses a backtracking algorithm to systematically explore all possible domino placements. When a placement violates a constraint, the algorithm "backtracks" to try a different option.

How it works:

  1. Choose a pair of adjacent empty cells
  2. Try placing a domino on these cells
  3. Check if constraints are still consistent (no rule violated yet)
  4. If valid: Continue to the next empty cell
  5. If invalid: Remove the domino and try another
  6. If solved: We're done!
  7. If stuck: Backtrack to previous decisions

Interactive Demonstration

Watch how backtracking solves a simple puzzle with constraint violations:

8
Available Dominoes:

Step 1 of 6: Initial State

Start with an empty board. The green region must sum to 8.

We need to fill this 3×2 grid with dominoes. The green region (top-left 3 cells) must sum to exactly 8.

Optimizations

The solver includes several optimizations to reduce search space:

  • Constraint Propagation: Check constraints immediately after each placement (e.g., pruning when partial sums already exceed targets)
  • Avoid Isolated Cells: Don't create cells that can't be paired with dominoes
  • Skip Duplicate Dominoes: Don't try both orientations for symmetric dominoes (e.g., 3|3)
  • Region Solvability: Verify each region can still be satisfied with remaining dominoes
  • Min/Max Sum Bounds: Calculate minimum and maximum possible sums for each region using remaining empty cells to prune impossible branches early
  • Parity Checks: Ensure remaining uncovered cells form regions with even cardinality so they can be tiled by 1×2 dominoes

Computational Complexity

Solving Pips exactly is a finite-domain constraint satisfaction problem (CSP) and is exponential in the worst case (NP-hard style). This means there's no known algorithm that can solve all instances efficiently. In practice, our backtracking approach with pruning and propagation makes typical instances very fast.

Easy puzzles typically explore hundreds of configurations, while hard puzzles may explore tens of thousands before finding a solution. Some puzzles may even have multiple valid solutions.

Ready to See It in Action?

Watch the backtracking algorithm solve real NYT Pips puzzles step-by-step with our interactive visualizer!

Try the Visualizer →