Intuitive example of an NP problem I was talking to a student today, and explaining that NP problems are hard to solve, but easy to verify.  I used password encryption/decryption as an example, but he got stuck.  He was unable to fathom how, given the hash, you couldn't just reverse your steps backwards to the password.

I started explaining a bit about encryption, but I came to think that my example was fundamentally not a very good one.  My goal is not to get into the weeds with encryption, my goal is to be able to explain what an NP problem is in a really intuitive way.

What is a clear analogy or example to describe NP?
If your student has tried it once, you can use sudoku as an example (it does not work so well if the student has never heard of it). 


Given a completed sudoku grid, write a program that verifies that it is valid: your student can probably write this simple program in a few minutes, or if you give the answer see that it is really easy.
Given an incomplete sudoku grid, write a program that completes it. Much harder (although semi-naive backtracking works well for 9x9 grids)!


It gets even better because, if you already gave the Map coloring (or graph coloring example), you can show easily that a 9x9 sudoku is just a particular instance of graph coloring and this becomes a good example for NP-completeness. (Just remark that a 9x9 sudoku is just a graph where each vertex corresponds to a cell in the sudoku, and an edge between two vertices means that the two corresponding cells are in the same row, column or block. Once a graph is built, try to 9-color it).