The Witness (trailer here) is not a game about solving puzzles, but rather about learning how to be able to solve puzzles. Broadly, it's a game about being perceptive, about teaching and understanding, and about discovery. The Witness is devoid of direct explanations or descriptions, yet successfully invites players to naturally learn the rules of the world around them while adopting a mindset of attentiveness.
The ingenuity of the game comes from the fact it takes the "solve line puzzles on grids" mechanic and toys with it as much as possible, squeezing absolutely everything out of it. The grids themselves serve as an input method, a means of interaction with your environment—the game is much more than hundreds of line puzzles on an island. Through these puzzles, however abstract, The Witness does not only (greatly) challenge players, but also incites real human emotion—glee, annoyance, excitement, hatred, wonder, elation.
The Witness is an ideal example of how a game should be—while it may only appeal to a relatively small subset of players, it appeals to this group greatly, rather than appealing to many players mildly without being overly impressive to anyone. It does not try to please all players, and actively rejects the "low risk–high reward" mold common to the modern video game industry. It's also not every game that necessitates the player getting a notebook of graph paper to solve puzzles, or at least exiting the game window to visualize one's thoughts using Microsoft Paint.
The Witness teaches players how to communicate. Working within the boundaries of the game's in-game "language," and using puzzle panels as means of expression, players engage in trial and error, receive positive and negative reinforcement, and gradually acquire more knowledge of how to piece together the basic building blocks of The Witness' language. While the game does not have a central narrative available to players from the beginning or a readily-available story forcibly tying together the puzzle-based gameplay found throughout different regions of the island, it does communicate—nonverbally (until the very end), presenting players with this arbitrary language, and giving them the tools to learn and utilize it. To quote Luis Antonio, Art Director for The Witness:
Just by solving panels, making mistakes, trying to get variety in shapes, colors and movement, you get a narrative. Tracing a puzzle can be broken down, from the starting circle, going through the thought process and arriving at the end cap, with a whole set of emotions in between, from getting the wrong shape, seeing a cable lit up, or the whole panel turning off in your face.
The Witness' success comes from the intertwining of its atypical, communicative nature and narrative with the very gameplay of the game itself. (Note that Braid, another game from developer Jonathan Blow, does this too; while Braid experimented with or happened to exhibit this characteristic, The Witness deliberately and purposefully pursues it.)
So, why "The Witness"?
The P versus NP problem, a major unsolved question in computer science and branches of mathematics such as complexity theory, asks: "Can every problem whose answer can be checked quickly by a computer also be solved quickly by a computer?" The definition of a problem in NP, e.g. puzzles in The Witness, is that, given a candidate solution, there exists a way to verify that the solution is correct in polynomial time. As we know, The Witness is more about the discovery of a verifier as opposed to finding an actual, specific solution to puzzles. In mathematical terms, such a verifier is called a witness. The game involves you, the player, searching for the witness to various puzzles.
I read and discussed this article live on the April 29th episode of Design Oriented, a show by Richard Terrell about game design and language.