There is a specific kind of puzzle frustration that is not your fault. You are stuck, you cannot see the move, and you assume a cleverer person would spot it instantly. Sometimes that is true. Sometimes the puzzle belongs to a class that computer scientists have formally proven to be hard - meaning no known method solves it except, essentially, by trying possibilities.

Knowing which puzzles are in that class is oddly comforting, and it changes how you should approach them.

What "computationally hard" actually means

The relevant idea is NP-completeness. Informally, a problem is in this class when a proposed solution can be checked quickly, but finding one appears to require searching an enormous space with no reliable shortcut.

The critical word is "appears". Nobody has proven that no fast method exists - that is the famous open question in computer science - but decades of effort have found none, and all problems in the class are equivalent in the sense that a fast method for one would give a fast method for all.

For a player, the practical meaning is this: in an NP-complete puzzle, there is no substitute for systematic search. Pattern recognition helps, experience helps, but at some point you have to try things in an organised way, because no amount of insight collapses the problem.

Which puzzles here are in that class

A surprising number of familiar puzzles have been formally shown to be NP-complete in their generalised forms - that is, when you scale them up to arbitrary size rather than the fixed small board you usually see.

  • Nonograms - the picture-logic puzzles - are NP-complete. Deciding whether a given set of row and column clues has a consistent solution is genuinely hard in general.
  • Sokoban is harder still. It is PSPACE-complete, a class believed to be even more difficult than NP. This is why Sokoban levels that look small can defeat you for hours - the solution length itself can grow explosively.
  • Rush Hour, generalised to arbitrary board sizes, is also PSPACE-complete.
  • Klotski and sliding-block puzzles in general share that difficulty - finding the shortest solution is hard even when a solution is known to exist.

Meanwhile Towers of Hanoi is the opposite: it has a known closed-form optimal solution of 2n - 1 moves and a simple recursive strategy that always works. It is long, not hard. That distinction - lengthy versus genuinely difficult - is worth internalising.

Why this changes how you should play

If a puzzle is in the easy category, being stuck means you have missed something and staring harder is reasonable.

If it is in the hard category, being stuck may simply mean you are at the point where search is required. The right response is different:

  • Be systematic rather than inspired. Work through possibilities in a fixed order so you know what you have eliminated.
  • Look for forced moves first. In nonograms, fill everything that is logically certain before guessing anything - the certain deductions often cascade.
  • Recognise dead ends early. In Sokoban, a box pushed into a corner is permanently stuck. Learning the standard deadlock patterns saves more time than any amount of forward planning.
  • Undo is a tool, not a failure. If the problem genuinely requires search, backtracking is the correct algorithm rather than an admission of defeat.

That last point deserves emphasis because it is counter-cultural. People feel that using undo is cheating. In a problem where search is provably necessary, refusing to backtrack is refusing to use the only method that works - and the same argument applies to the patience games, where replaying a lost deal with undo is how you find the line that existed all along. Spend an evening with FreeCell online and almost every deal is winnable, so a loss means the search was too shallow rather than the puzzle unfair.

The generalisation caveat

An honest qualification: these hardness results apply to the generalised versions - arbitrarily large boards. The specific puzzles you play here are small and fixed, and a computer solves them instantly.

The results are still meaningful for a human player, though, because they tell you something about the structure of the difficulty. A puzzle whose general form requires search does not become insight-based just because it is small; it becomes a search you can complete in your head. The character of the thinking is the same.

The puzzles that are hard in a different way

Not all difficulty is computational. Several games here are demanding for reasons that have nothing to do with search complexity.

Memory is purely a recall problem - no reasoning at all, just retention. Simon tests sequence memory under time pressure. Lights Out looks like trial and error and is actually solvable with linear algebra over a two-element field, which makes it one of the most elegant puzzles here once you know the trick. Flow and Water Sort reward spatial planning more than systematic search.

And 2048 is different again: it has a random element, so it is not a puzzle in the strict sense at all but a strategy game against chance. That shifts the required skill toward keeping your options open rather than solving - which is why the standard advice is to keep your largest tile in a corner and never disturb it, the same "preserve your structure" principle that governs the tile games.

If you want to see that instinct at full speed, play Tetris online - the entire skill is maintaining a board that can accept whatever arrives next, which is the real-time version of the same idea.

Go and lose a few

Try a nonogram and force yourself to fill only cells you can prove, marking uncertain ones rather than guessing. Most players find they can get much further than expected by pure deduction, and the point where deduction genuinely runs out is a real and identifiable moment.

Then try Sokoban and pay attention to how quickly a wrong push becomes irreversible. The rules hub covers every puzzle, the logic puzzle FAQ is a useful primer, and the glossary names the terms.

For the impossibility result hiding inside the humble sliding puzzle, see the companion piece.