The computer game "The Witness" contains various puzzles based on a finite square grid graph arranged in the usual way. A path must be found from a given point on the edge to another. Each square can contain a symbol that describes additional constraints.

The Witness screenshot showing a 4x4 grid A 4x4 grid.


The Witness screenshot showing a 4x4 grid with a path, this path covers 9 nodes and 8 edges A 4x4 grid with a path.


For simplicity and to get speedily to the maths I will describe a reasonably similar but simplified version of the game. This version contains "separating" puzzles where only empty squares and tiles containing coloured "dot" symbols are used. And "pairing" puzzles where only empty squares and the mono-coloured "star" symbol is used.

The Witness screenshot showing a 4x4 separating puzzle with a path that solves it A 4x4 separating puzzle with a path that solves it (middle).


The Witness screenshot showing various 4x4 pairing puzzles Various pairing puzzles.

Both types of puzzle involve making envelopes between the path and the edge of the grid to enclose groups of symbols. Dots must be in seprate regions (envelopes) to dots of other colours, whereas stars must be in pairs.

In separating puzzles the existence of any group of 3 adjacent squares in a puzzle that form the shape of the L shaped tromino with entirely dissimilar colours of dot symbols are unsolvable.

The same is true of a two colour 2x2 square of dot symbols with diagonally opposite same colours.

The same sort of check also exists for the pairing puzzle except that the shape is that of 5 square pentomino that is in a "+" shape.

Q: Can the shapes above that indicate a puzzle is unsolvable be reduced in size, or the check otherwise be made simpler?

  • 2
    $\begingroup$ Presumably those are not the only conditions that can make the puzzle unsolvable. $\endgroup$
    – Joffan
    Oct 5 '17 at 18:18
  • $\begingroup$ Thats right, it still might be unsolvable anyway. Also these puzzles are strikingly hard considering they look so straightforward which I guess might indicate a steep time complexity, like in the game "2048". $\endgroup$
    – alan2here
    Oct 5 '17 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.