Is there any puzzle or game which cannot be decided in polynomial time and whose problem description can be easily understood by a kid? If it is a fun puzzle so much the better.
I want to demonstrate to a high school student the difference between P and NP class of problems using an example. Also, if there's some simple algorithm to show that it can be decided in polynomial time by a non-deterministic machine that would be a great bonus.
There is a list of a bunch of games that are NP-hard here: https://www.ics.uci.edu/~eppstein/cgt/hard.html You might also enjoy this list of Nintendo games that are NP-hard: https://jeremykun.com/2012/03/22/nintendo-np-hard/.
Some well-known games that can be proven to be NP-hard (in some form or other) include Tetris, Minesweeper, Checkers, Chess, Dots and boxes.
I think Dots and Boxes might be a particularly surprising and accessible one -- it's rather mind-blowing that such a simple-seeming game hides such complexity.
Caveat: do understand that in many of these cases, we're actually considering a variant of the game. Many games are finite, so there are only finitely many positions, and thus can't literally be NP-complete -- so instead we consider variants. For instance, instead of chess on a 8x8 board we consider a variant with a $n \times n$ board, or something like that. The general point still applies but there are technical details that you should make sure you understand before using this in a classroom.
One example that's familiar to many people is dishwasher loading. You have a set of items (3-dimensional objects) you want to fit in a dishwasher. Many people have experienced that greedy methods and heuristics don't work: you load up the dishwasher using some sensible method and things don't fit. But then if you start from scratch and load things slightly differently, there's plenty of room.
The dishwasher example is nice because it's relatively familiar, and gives some intuition about why NP hardness problems are really hard: fitting things nicely locally doesn't necessarily give a good global solution. It's also truly an NP-hard problem, even in very simple cases (like all your dishes are cubes).
It's obvious that an NP machine can solve dishwasher loading in polynomial time (as it can try all ways of loading the dishwasher non-deterministically). On the other hand, most natural NP-hard problems can be solved using something like this so I'm not sure if that's the structure you want.
A second example that's likely even more familiar is three-dimensional pathfinding. Many people have experienced the struggle of (say) trying to move a couch into a new apartment. Shortest path in three dimensions in general is NP-hard (see New Results on Shortest Paths in Three Dimensions by Mitchell and Sharir for example). Some disadvantages of this problem are that the technical aspect is more difficult, and that everyday cases are often easy. (Aside from moving couches into small apartments I solve 3-dimensional shortest path every day without much issue.)
