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.

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.

+-+-+-+-+ +-+-+-+-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|| ||+-+-+-+-++-+-+-+-+

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

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.