I read a while ago a researcher's website specialized in puzzles. He claimed (informally) the only really "deep" puzzles that can keep you hooked are based on N

I read a while ago a researcher's website specialized in puzzles. He claimed (informally) the only really "deep" puzzles that can keep you hooked are based on NP-hard (or harder) problems. Polynomial-time puzzles according to him just depend on finding a "trick" after which you can solve most puzzles relatively quick. Specially O(n) puzzles. Which is the case for this planarity puzzle! I did enjoy the few ones I did, perhaps I didn't "get" the linear-time algorithm right away. NP-hard puzzles otoh, are hopeless for hard instances and general algorithms. Both the designer has to give it more thought on making instances that are not worst-case, and you have to rely not on general-case algorithms but an increasing set of heuristics and intuition to solve. Brute force is completely hopeless. The same goes for two-player games. If the game can be solved in polynomial time, one of the players will find a trick (the polynomial time algorithm essentially) to always win (or depending on the game always draw).