The Witness Puzzle Solver (SPOILERS!)
This is a tool for solving all of the non-environment puzzles in the video game
The Witness. It provides an
interface for inputting puzzles similar to the panels in the game. It finds the
simplest solution and displays it in the grid. You can also configure the solver
to only show part of the solution if you just need a hint.
You can try out the solver here:
https://overv.github.io/TheWitnessSolver/
Algorithm
Currently a very simple branch-and-bound algorithm is used that walks through
all possible paths from each starting node and evaluates if the current path
forms a correct solution when it hits an exit node.
Even just verifying a solution for the puzzles with tetris blocks appears to be
an NP-complete problem
so the algorithm is unlikely to become more efficient. Most of the effort should
probably be dedicated to finding heuristics for the bound conditions to reduce
the depth of the search tree.
This solver does not attempt to find the "simplest" solution, because that would
require an exhaustive search that eliminates many optimisation opportunities to
keep the performance reasonable.
The areas split up by the solution path are found incrementally, which means
that for every step in the path only the last area has to be reexamined. This
is much faster than running flood fill from scratch for every proposed solution
and allows for early termination decisions, because other areas are known to
longer change with future steps.
Similar to the first-fit decreasing bin packing algorithm, tetris puzzle
solutions are verified by trying to fit the largest tetris blocks within an area
first, which allows for detecting nonsensical solutions earlier. Note that
unlike the bin packing algorithm, all possible combinations will be attempted if
necessary.
Prefer required neighbour nodes
If multiple unvisited neighbour nodes are available, try visiting the required
nodes first. This can avoid a lot of dead end solutions early on.
Segregation optimization through auxilary required nodes
If differently colored squares are direct neighbours, then the edge between them
must be part of the correct solution path. That means that the endpoints of
that edge are required nodes in the path. By checking for these (extra) required
nodes in the solution check, the full segregation check doesn't need to run most
of the time, which saves a lot of time.
Terminate a path if finished areas are already wrong
If an area that cannot be revisited already fails the segregation or tetris
checks then there is no point going on.
Rules
This is a list of the mechanics as implemented by this solver:
Path
The path must be a self-avoiding walk starting at a start node and ending at an end node
Hexagons
Nodes or edges with a hexagon must be included in the path
Squares
For every region R, all squares in R must share the same color.
Suns / Stars
For every region R, if a sun of color X in in R, then there must be exactly two elements of color X in R.
Tetris Pieces
For every region R, R must exactly accommodate all the tetris pieces represented in R.
Hollow Squares
For every region R, let H be the total number of hollow squares represented in the region (that is, groups just contribute their size, and the shape is ignored).
For some choice of H individual tetris blocks, R must pass tetris validation (the step described above) when these pieces are removed, but not if fewer than H blocks are removed.
Cancellation symbols
For every region R, let K denote the number of cancellation symbols in R.
For some choice of K (non-cancellation) elements from the region, validation must pass (that is, all the rules described above must pass) when these elements are removed, but not if fewer than K elements are removed.
Notable implementation discrepancies
Here are some things that are different from the game:
- Perhaps most importantly, Cancellation symbols will not respect hexagons -- they only consider entities in the interiors of cells.
- Hollow tetris cubes are implemented only depending on the total amount of hollow blocks in a region, disregarding shape.
For the vast majority of puzzles in the game, this is acceptable.
It's not completely clear how respecting the shape of hollow squares would work, as there were very few puzzles in the game using this mechanic.