My first introduction to the n-Queens problem was the game The 7th Guest. One of the mini-games was placing eight queens on the board, but they didn't tell you what you had to do. They just gave you a board and eight queens to place. As you placed one, any others that you had placed that were now in danger would disappear. Eventually you figured out that you had to get all eight on there.

My friend and I spent about an hour trying to figure it out when we were 16 or so. He's a mathematician studying elliptic curves now.