triangulation-maze
TypeScript React Vite SVG
Play the puzzle Runs entirely in the browser — no accounts, no external requests during play.
A convex polygon is cut into triangles by N − 3 non-crossing diagonals. Click one and it flips: the two triangles beside it form a quadrilateral, and the diagonal is replaced by that quadrilateral’s other diagonal. Dashed pink lines show a target triangulation drawn on the same polygon. Match every one of them and you win.
The catch is the colours. A freshly flipped diagonal is green and available; its neighbours toggle between green and red, and a red diagonal cannot be flipped. Diagonals that sit on the starting triangulation are exempt and stay flippable forever, drawn in white over a faint grey underlay of where the puzzle began. So the moves that are geometrically legal and the moves you are permitted to make are not the same set, and it is not obvious that the target is reachable at all. It always is: Sylvain Gravier and Charles Payan proved in 2002 that any starting and target triangulation of a polygon, for arbitrary N, can be joined by a permitted sequence of flips — by reducing the claim to the Four Color Theorem.
Origins and mathematical background
I built the first version of this while looking for a proof of the Four Color Theorem (4CT), and shared it as a Wolfram Demonstration in 2012. At the time I naively thought an elementary proof of the 4CT might be within reach, and turning the statement into a game was a way to get a feel for it.
I did not find that proof. What I did find was a proof that this game can always be won if the Four Color Theorem is true.
I did not know then that this had already been conjectured by Shalom Eliahou in 1999 and proved by Gravier and Payan in 2002. Finding out afterwards that the reformulation of the 4CT in terms of a constrained flip sequence had been found before was a pleasant surprise rather than a disappointment — I like meeting people mentally by arriving at the same idea; it makes you feel connected. Garry Bowlin and Matthew G. Brin elaborated the associahedron side of the connection in 2013, through their study of colored paths in associahedra and planar graph coloring. Karin Baur, Diana Bergerova, Jenni Voon, and Lejie Xu give a recent overview of coloured triangulations, coloured flips, and the Four Color Theorem connection, together with new results on the structure and connected components of coloured flip graphs.
- Shalom Eliahou, Signed Diagonal Flips and the Four Color Theorem, European Journal of Combinatorics 20(7), October 1999, pp. 641–647.
- Sylvain Gravier and Charles Payan, Flips Signés et Triangulations d’un Polygone, European Journal of Combinatorics 23(7), October 2002, pp. 817–821.
- Garry Bowlin and Matthew G. Brin, Coloring Planar Graphs via Colored Paths in the Associahedra, International Journal of Algebra and Computation 23(6), 2013, pp. 1337–1418, World Scientific.
- Karin Baur, Diana Bergerova, Jenni Voon, and Lejie Xu, Flip graphs of coloured triangulations of convex polygons, arXiv:2402.06546 [math.CO], submitted 9 February 2024.
Eliahou and Gravier–Payan put the signs on the triangles rather than the diagonals: each triangle carries a + or a −, and a flip is permitted when the two triangles on either side of the diagonal carry the same sign. That is what the colours are. A green diagonal separates triangles of equal sign, a red one separates opposite signs — a slightly different formulation of the same rule.