Consider this generalization of the $N$-queens problem:
The $N + k$ Queens Problem: Let $N > 0$ and $k \geq 0$ be integers. On an $N \times N$ chessboard, can you place $N + k$ queens and $k$ pawns so that any two queens on the same row, column, or diagonal have at least one pawn between them?
We've had many math and computer science undergraduates working on projects related to this problem. For more information, please see the $N + k$ Queens Problem Page at http://npluskqueens.info .