# Are there any popular puzzles with polynomial-time algorithms?

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?

• Related question on cstheory.SE – JeffE May 29 '14 at 1:08
• This question appears to be off-topic because it belongs on cstheory.SE – Xynariz May 29 '14 at 21:16
• @Xynariz If anything I would be inclined to say cs.SE rather than cstheory (this isn't a research-level question by any means); but I would say that my particular question (not 'what is the complexity of X popular puzzle' but almost its converse, 'are there any popular puzzles with complexity Y') makes it more appropriate for this site than that one... – Steven Stadnicki May 29 '14 at 21:28
• True, it may belong on cs.SE (I'm not 100% sure of the difference between cs.SE and cstheory.SE). The reason I think it belongs there, rather than here, is that almost all of the cs.SE audience understands puzzles, and could possibly give you examples, where I doubt that the general puzzling.SE user could even understand the terms in your question (NP-Complete, etc.). Personally, I find the question intriguing, I just don't believe it belongs here. – Xynariz May 29 '14 at 21:32

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.

• 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.

• my twisted lightout version wasnt been solved by linear equation system , i know its possible though – Abr001am Apr 5 '15 at 11:31
• Does linear algebra suffice for "lights out" if one is only allowed to press buttons when they are lit? Linear algebra will readily indicate which buttons need to be pushed an odd or even number of times, but I don't think it provides the sequence in which that must occur. – supercat May 28 '15 at 19:50
• @supercat Good question! I think so. Say you have a light $L$ which is off but you want to press it. You can find a path from $L$ to some other light which is currently on. By pressing along the path and back, you can press $L$ once and press everything along the path twice. However, for the problem of solving a Lights Out puzzle in the minimum number of presses, I conjecture it's NP-complete for both variations. – Lopsy May 28 '15 at 22:22
• Unless I'm missing something, it's possible to take any 3SAT problem and turn it into a lights-out problem. Use two pairs of buttons for each variable and two pairs for each clause. Call one pair of buttons for each variable T and F; the other t and f; call one pair for each clause X and Y, and the other P and Q. Each uppercase button should toggle its own light and that of its partner. Additionally... – supercat May 28 '15 at 23:17
• Each variable's T should toggle t for that variable and X for every clause that would be satisfied if that variable is true, and each variable's F should toggle its f as well as the X of every clause that would be satisfied if it's false. Each clause's Y should toggle its P. Start with every T, F, and P lit, and all other lights off. The only way to turn off P, Q, X, and Y for a clause will be to have something turn on its X, hit its X and Y, and have something turn off its X. Each variable can be used to either hit the Xs of clauses that are satisfied when it's true, or when it's false,... – supercat May 28 '15 at 23:24

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:

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'.

• Downvotes noted and I've clarified my answer - am I missing your point? – Lawrence Apr 5 '15 at 11:21
• number theory puzzles are not solved using linear methods , i have created some and none of them was been solved by a direct approach , it was always bruteforced , btw , im not the one who donvoted you – Abr001am Apr 5 '15 at 11:28
• +1 The really interesting question is, what's the algorithmic complexity of the 'aha moment'? ;) – A E Apr 5 '15 at 11:35
• @Agawa001 Thanks for clarifying - I didn't realise from your question that you were referring to just number theory puzzles. The level of interest in puzzles is probably related to the effort needed to solve them as well as the elegance of the final solution. For calculation-style puzzles, the higher the computational complexity, the more effort needed. Provided you get a nice result in the end (or a nice general form) and it doesn't take excessively long to solve, you probably do have the correlation you suggested. – Lawrence Apr 5 '15 at 11:46
• @AE :) indeed. Given how fast some people come up with solutions to puzzles on this site, the best-case complexity can't be all that high :P . – Lawrence Apr 5 '15 at 11:55