Are there any popular puzzles with polynomial-time algorithms?

Question

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?

Answer 1

• Lights Out puzzles have a polynomial time algorithm by linear algebra.
• "Draw this shape without picking up your pencil" puzzles have a polytime algorithm which follows from the proof of which graphs have Eulerian circuits.
• Sliding puzzles like the 15-puzzle are easy (though hard to solve in a minimal number of moves).

IMO these examples kind of prove your assertion. None of them are popular anymore (the last time I saw Lights Out was what, middle school?), and I bet this is because once you learn the algorithm, they're boring.

• For a more nontrivial but lesser known example, take "orb puzzles" from the Deadly Rooms of Death video game series. Orb puzzles consist of a bunch of doors, and a bunch of orbs which control them. For each orb and each door, the orb either opens, closes, toggles, or does nothing to the door. Orbs may be triggered in any sequence, as many times as you want. The objective is to find a sequence of orb hits which leaves all the doors open.
  
  Players used to include orb puzzles in their custom levels a lot. Then mitchthro found a polytime algorithm here. Now orb puzzles are basically dead. (But I doubt the algorithm killed them; I think they died because players find them repetitive and unfun.)

I wonder if there are any popular puzzles which fall to linear (or convex) programming.

Answer 2

I suspect the complexity class is not too important. In the example of Sudoku, the NP-complete problem is "given a partially filled in $n \times n$ grid, state whether it can be completed to a legal arrangement". The popular puzzle is "given a partially filled in $9 \times 9 $ grid that is known to have a unique solution, find that solution". In the popular puzzle, we don't care how the complexity depends on $n$, just that the size we do has the correct difficulty. Similarly, the substitution ciphers that are in the daily paper have $ 26! $ possible keys, an enormous number, but the structure of English makes them soluble.

Jumble, cryptarithms, and bridge problems are some that have stayed around and seem to have a lower complexity class.

Added much later: one of the things that makes Sudoku appealing is that if you find one thing you don't know where in the grid to look for the thing(s) you should now find. This seems to be a common thread for the NP-hard problems, that you need to find a global solution because a problem in one area can propagate to affect the solution in other areas. I think it makes puzzles more appealing. In that sense there is a common thread between interesting puzzles and complexity class.

Answer 3

The OP asks two questions:

1. "... whether there are any fairly popular puzzles that are still 'easy' in an algorithmic sense"; and
2. "What other examples are there of puzzles that have maintained popularity despite having relatively mechanical solutions?"

This answer only deals with the first and argues that there are popular puzzles that are 'easy' in an algorithmic sense although 'difficult' in a solution-formulation sense.

Algorithmic complexity is usually expressed as a measure of the time or space taken in terms of a measure of the inputs. Different solutions to a given problem can have different complexity. For example, quicksort is an algorithm for sorting lists and has average case time complexity $O(n \log n)$ in terms of the number of items to be sorted. Bubble sort is another algorithm for sorting lists and has average case time complexity $O(n^2)$.

Although there are problems whose solutions always have high algorithmic complexity, the lateral thinking required for good puzzles often makes the formulation of the solution more difficult than the computing the solution itself. As a measure, algorithmic complexity doesn't really help because by definition it is a measure of only the solution, not of the formulation of that solution.

Have a look at the 'questions' page: click on 'questions' above and then on 'votes'. Using votes as a proxy for popularity, the current list has quite a few popular puzzles with solutions that have low algorithmic complexity.

Top 6 currently:

1. https://puzzling.stackexchange.com/questions/4304/how-to-get-to-an-island-with-a-tree-in-the-middle-if-all-you-have-is-rope
2. A double-agent with a conundrum
3. Internship Available!* - Figure out what you're being asked to do before you sign up
4. Merlin and Hermes: Mysterious Lines
5. https://puzzling.stackexchange.com/questions/1968/3-impossibly-intelligent-mathematicians
6. Paying the Troll toll

Of these, only the "3 impossibly intelligent mathematicians" puzzle is really amenable to 'mechanistic' solving. In most of the others, once the 'aha' observation has been made, computing the solution is trivial.

One final note: most of these puzzles don't have significant structural variability in their inputs, so algorithmic complexity is not a good measure of whether these particular kinds of puzzles are 'easy' or 'difficult'.