Recently, I've been thinking about the types of games that people like to play most on their phones and at parties. Games that are NP-complete seem to strike the right balance - they're challenging, but don't take too much practice. Polynomial time games (like Tic Tac Toe and Connect Four) feel too easy and exponential time games (like chess and go) have steep learning curves.
In NP-complete games, you can quickly verify whether a move is valid, but it is hard to decide what you'll do on your turn.
- Battle Ship - a decision problem
- Bejeweled & Candy Crush
- Mastermind - proven to be a 3 SAT problem.
- Sudoku - instance of the exact cover problem.
- Set - instance of the set packing problem.
Seems like it may be worth going through Karp's 21 NP-Complete Problems to brainstorm some new games.