patternMinor
Puzzle/game of NP class for a high school student
Viewed 0 times
studenthighschoolgameforclasspuzzle
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#71052, answer score: 2
Revisions (0)
No revisions yet.