The 8 Queen Problem
Here's a puzzle: Can you place eight Queens on a chessboard so that none of them can attack each other?
It seems simple enough—start putting a few pieces on the board and find out. If you start doing this, you'll see that it's a bit tricky, because the Queens are able to traverse the board in any direction. But if you spend some time fiddling, you'll likely be able to figure out a solution. (This is also a common problem in Computer Science courses, with the idea being to make a computer figure it out for you.)
The more interesting question is: How many possible placements are there? Well, some quick math (shown in the video below) tells us that there are 4 billion ways to arrange these pieces on the board, though only 12 placements are actually valid, unique solutions. In this video, watch Dr. James Grime work out this famous math puzzle:
For more on the problem and its solutions, Wikipedia has an excellent overview.