P vs NP: Instructive example of when Brute Force search can be avoided To be able to explain the P vs NP problem to non-mathematicians I would like to have a pedagogical example of when Brute Force-search can be avoided. The problem should ideally be immediately understandable and the trick should neither be too easy nor too hard.

The best I've come up with so far is

SUBSET_PRODUCT_IS_ZERO

The problem is easy to understand (given a set of integers, can a subset with product 0 be formed?), but the trick is too easy (check if 0 is among the given numbers, i.e. it's not necessary to look at a lot of subsets).

Any suggestions?
I recommend Jenga!

Assuming you have two perfectly logical, sober, and dextrous players, Jenga is a perfect-information two-player game, just like Checkers or Go.  Suppose the game starts with a stack of $3N$ bricks, with 3 bricks in each level.  For most of the game, each player has $\Theta(N)$ choices at each turn for the next move, and in the absence of stupid mistakes, the number of turns is always between $N$ and $6N$.  So crudely, the game tree has $N^{\Theta(N)}$ states.  If you explored the game tree by brute force, you might spend exponential time to find a winning move or convince yourself that you can't win.

But in fact, Uri Zwick proved in 2005 that you can play Jenga perfectly by keeping track of just three integers, using a simple set of rules that you can easily fit on a business card.  The three numbers you need are


$m =$ the number of levels (not counting the top level) with three bricks.
$n =$ the number of levels (not counting the top level) with two bricks side by side.
$t =$ the number of bricks in the top level (0, 1, 2, or 3).


In fact, most of the time, you only have to remember $n\bmod 3$ and $m\bmod 3$ instead of $n$ and $m$.  Here is the complete winning strategy:



Here I-I means you should move the middle brick from any 3-layer the top, II- means you should move a side brick from a 3-layer to the top, -I- means you should move a side brick from a 2-layer to the top, and the bob-omb means you should think about death and get sad and stuff.  If there's more than one suggested move in a box, you can choose any one of them.  It's trivial to execute this strategy in $O(1)$ time if you already know the triple $(m,n,t)$, or in $O(N)$ time if you don't.

Moral: Jenga is only fun if everyone is clumsy and/or drunk.