I remember playing The Witness when it came out. Though it got a bit too difficult for me at some point, I remember the beautiful and serine environment, the feeling of discovery and achievement. I had a blast. A decade later, maybe it’s time for me to get back.
Yeah I liked it! I felt like I was too dumb for some of the puzzles lol.
People underestimate how hard the puzzles are. In computational complexity terms, the hardest puzzles in the witness are harder than sudoku.
Doesn’t that depend on the sudoku though?
Or do you mean that there were puzzles that were harder to solve than even the hardest sudokus in the world?
In terms of “computational complexity” we mean the following:
Consider the following generalization of Sudoku. There is a number, N, and a grid of squares with N2 squares per side. (So the grid in total has N4 squares.) Each row and column of the grid has N2 squares. The grid therefore contains an N2 number of NxN subgrids (this corresponds to the 3x3 boxes in regular sudoku, called Houses). The puzzle is to fill each row, column, and house with the numbers from 1 to N2 with no duplicates.
The complexity is then a measure of how much harder the puzzles get when N is increased. Sudoku is a classic example of a so-called “NP-Hard” problem. Most puzzles that people think of as difficult are NP-hard. The ELI5 is that given a claimed solution to a sudoku puzzle, you can check if it really is the solution quickly (where again “quickly” is in terms of N). This is not true for the hardest types of puzzles in the witness.
This is only a proxy for how difficult humans will find the smaller puzzles but it’s remarkably accurate. The hardest puzzles using every mechanic from the witness (realistically, only using two of them including the last one) are going to be much harder for a human than the hardest sudokus.