n-queens problem is a very interesting problem.  Especially when you start imagining more than 2 dimensions and start thinking d-dimensions it becomes an even more interesting and challenging combinatorics problem.  The link also points to some applications including traffic control, which makes sense.