All projects
Prolog

Pips

A solver for the NYT Games Pips domino puzzle written in pure SWI-Prolog logic programming, where a single reversible predicate can either check a proposed solution or compute one from scratch through backtracking.

View on GitHub
Prolog Logic Programming Constraint Solving

Pips

Final project for the Programming Languages course at the Universitat de les Illes Balears. A solver for Pips (the NYT Games domino puzzle, 2025) written in SWI-Prolog as pure logic programming — only predicates, clauses and backtracking, with no if-then-else, no higher-order predicates and no libraries beyond what was seen in class. Given a set of regions with constraints and a bag of dominoes, the same predicate can either check a proposed solution or compute one from scratch.

The puzzle

A Pips board is made of regions (groups of cells, each with a constraint), a list of dominoes to place, and a solution that assigns every domino to two adjacent cells. A placement is valid when every cell is covered by exactly one domino half, the placed dominoes match the given bag, and every region constraint holds — equals (all cells share the same value), sum / less / greater (the cell values sum to, below or above a target) or empty (no constraint at all).

About

The main predicate is solucio_pips/3, and it works in both directions depending on which arguments are instantiated: with the solution bound it checks it (adjacency, coverage, the domino multiset and every region constraint), and with the solution unbound it solves the puzzle by placing each domino on adjacent free cells and letting Prolog’s backtracking find an assignment that satisfies every region. The code is split across several files:

  • pips.pl — entry point. Hand-written auxiliary predicates (list handling, sums, adjacency…) plus solucio_pips/3 and an efficient solucio_pips_rapid/3 variant with incremental pruning (green and control cuts, no duplicate placements).
  • puzzles_pips.pl — knowledge base of puzzle/5 facts.
  • pips_tauler.pl — prints the solved board to the terminal.
  • pips_proves.pl — automatic tests over the whole knowledge base.
  • pips_genera.pl — generation of new puzzles.
  • pips_clpfd.pl — an alternative CLP(FD) version kept in parallel to the pure one.
  • pips_web.pl + web/ — a static web interface; the Prolog side only exposes a JSON bridge and all the game logic stays in pips.pl.

Anything that could be a built-in (member, append, findall, maplist…) is instead written by hand with manual recursion, because the assignment only allows constructs introduced in class.

Executing the project

Requires SWI-Prolog (swipl). Load the project and try a puzzle:

?- [pips].
?- puzzle(20250818, easy, R, P, S), solucio_pips(R, P, S).      % check a solution
?- puzzle(20250818, easy, R, P, _), solucio_pips(R, P, S).      % compute the solution
?- puzzle(20250818, easy, R, P, S), imprimeix_tauler(R, P, S).  % draw the solved board

Web interface

The web front-end also needs PHP on your PATH. From the P2/ folder, start a local server:

php -S localhost:8000 -t web

then open http://localhost:8000. web/api.php only forwards each request to swipl; all the game logic lives in the Prolog solver.