All projects

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.

Prolog PrologLogic ProgrammingConstraint Solving
Built by Andreu Massanet Marc Morlà
Source

The problem

Project 2 of 2 for the Programming Languages course at the Universitat de les Illes Balears.

Solve the NYT Games domino puzzle with nothing but predicates, clauses and backtracking — no if-then-else, no higher-order predicates and no library beyond what was seen in class. Anything that could be a built-in (member, append, findall, maplist…) has to be written by hand with manual recursion.

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).

How it works

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.

Running it

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.