First, a little background: as I noted in my answer to another question here, most of the puzzles that seem to stay popular for extended periods of time are canonically 'hard' in an algorithmic sense: for instance, Rush Hour is known to be PSPACE-complete, Sudoku is known to be NP-complete, Nurikabe is (at least) NP-complete, etc.
My question is whether there are any good counterexamples to my assertion there; that is, whether there are any fairly popular puzzles that are still 'easy' in an algorithmic sense. A few examples spring to mind, one that doesn't really fit the rather nebulous abstract-puzzle crtieria I had in mind for this question, but a couple that do:
- Word search puzzles have a relatively trivial algorithm that takes O(m * n * s * |S|) time (specifically, comparisons) to find s words of total length |S| in an m×n grid. There are ways to make this somewhat better with string-matching algorithms like the Knuth-Morris-Pratt algorithm, but even the naive approach is usually 'fast enough'. This isn't really the sort of puzzle I'm after, though — it's more like a textual Where's Waldo than a deductive exercise.
- (Classical) Mazes can be solved efficiently by converting the grid into an abstract graph and then using basic pathfinding algorithms (e.g., breadth-first search) to find a route (the shortest route) from start to finish. This is definitely an example of the sort of thing I'm after — but I would argue that traditional mazes are rarer than they used to be for exactly this reason, and multistate mazes (which have gotten much harder) are much harder both for human and for algorithmic solvers; in the abstract, there can even be an exponential state-space blowup and I wouldn't be surprised to find hardness results for suitably general multistate mazes — in fact, the PSPACE-completeness for Rush Hour or hardness for Sokoban could be thought of as examples of this.
- Rubik's Cube obviously has an algorithmic procedure for solving (in fact, several); on the other hand, it's hard to even speak about hardness results for a 'fixed-n' problem, and my understanding is that solving cube-style puzzles (though possibly not the cube itself) can get algorithmically hard for higher n and/or higher dimensions.
What other examples are there of puzzles that have maintained popularity despite having relatively mechanical solutions?