solving triangle puzzles with a reverse lookup in the Witness

This page discusses spoilers for the triangle puzzle panels found in 2016's the Witness. If you're not familiar with this puzzle type, think carefully about whether you really want to read this or not.

the rule:

These puzzles, sometimes referred to as "discarded panel puzzles" or "dorito puzzles" can be found in isolated teaching examples throughout the island, but become important during the maze navigation section of the "Challenge". The rules for these puzzles are as follows: each square contains zero, one, two, or three golden triangles. If a square contains one or more triangles, it must contact the line on exactly that many sides on the line's journey from the bottom left corner to the top right one. If the square contains zero triangles, it doesn't matter how many line segments contact it.

examples:

	+-+-+-+-+     +-+-+-+-o
| | | | |     | | | | |
+-------+     +-----+-+
| | |1| |     | | |1| |
+-------+ +-> +-----+-+
| | | | |     | | | | |
+-------+     +-----+-+
|1| | |1|     |1| | |1|
+-+-+-+-+     +-+-+-+-+

+-+-+-+-+     +-+-+-+-o | | |1| |     | | |1| | +-------+     +-+-+---+ | |1|1| |     | |1|1| | +-------+ +-> +---+---+ |1| | |2|     |1| | |2| +-------+     +---+-+-+ |1| | |1|     |1| | |1|
+-+-+-+-+     +-+-+-+-+

+-+-+-+-+     +-+-+-+-o | |2|1|1|     | |2|1|1| +-------+     +-+-+---+
| |2|1| |     | |2|1| | +-------+ +-> +-+-+---+
|3|2|2|1|     |3|2|2|1| +-------+     +-+-+-+-+ |2| | | |     |2| | | | +-+-+-+-+     +-+-+-+-+

approaches to solving these puzzles:

I find these puzzles very hard to solve under pressure. In February 2016, an anonymous 2ch user posted a tool - the webcrow solver - that could solve these puzzles very quickly, but it intermingled its display and solution code, and there were no comments in the source. I was interested in understanding how it worked, in the hope that the programmer had discerned an algorithm for solving these puzzles that I could do in my head. Unfortunately, this was not the case.

The webcrow solver's insight is to use a reverse lookup table. There are 8,512 different ways of traversing the four-by-four grid, and each pattern of lines necessarily implies a matching number of triangles in each square - just count the number of line segments touching it, i.e.:

	+-+-+-+-o     +-+-+-+-+
| | | | |     |2|2|3|2|
+-+-+-+-+     +-------+
| | | | |     |2|3|2|1|
+-+-+-+-+ +-> +-------+
| | | | |     |1|2|3|2|
+-+-+-+-+     +-------+
| | | | |     |2|3|2|2|
+-+-+-+-+     +-+-+-+-+

With such a look-up table in place, it can then be inverted to get a list of puzzles (we might call the example above, reading left to right, top to bottom, puzzle "2232232112322322") that each point to a viable solution (which again, we might call, "up up up up right right right down left left down right right down left left down right right right up up up up".) Because squares with no triangles in them do not care about how many lines touch their edges, this solution also works for any puzzle that replaces one of the puzzle's numbers with a zero, e.g. "2232232102322322".

an example implementation of these ideas:

The following code shows an implementation of these ideas on a generic grid of m by n cells: triangle_solver.py

Interestingly, while this program gets slower and slower as you run it on larger grids (even 5 by 5 is very slow indeed), humans don't seem to deal with the time penalty of increasing complexity in the same way.

afterword:

My notes from my playthrough of The Witness
some of my notes from my playthrough of The Witness