Place eight queens on a chess board so that no queen attacks any other. (Yes, it can be done.)
When I was just a kid, they were using this problem in elementary programming courses to teach the use of recursion and backtracking.
A problem that can be solved by BruteForce (and doesn't suffer from CombinatorialExplosion).

This is a job for...EightQueensInManyProgrammingLanguages!*Or k-promising vectors*
*See http://www.cs.umu.se/kurser/TDBC91/VT02/lec13.html*

There are 12 unique solutions: http://www.ic-net.or.jp/home/takaken/e/queen/. This includes rotations only; if you include reflections, there are 6. On a physical chessboard, it matters whether the pieces are above or below the board, so a reflection is still "unique".*In a group theoretic sense, there's no such difference between rotational symmetries and reflectional symmetries; the pieces do not end up "below". This can profitably be regarded as a rotation through a fourth spatial dimension.*
I don't follow that, Doug. Any reflection is its own inverse. That isn't true for all rotations, only those (effectively) through 180 degrees.
*You're right. But why does that matter here?*
If you rotate through an extra dimension, you have to be sure that the end result is still in the same 3-D section. That necessitates making a 180-degree turn, which is self-inverse. All reflections can be considered this way. More notably, you can notice that the board is essentially 2-D, and that placing queens above or below the board only matters for the convenience of the players.
[A reflection is equivalent to a rotation through 180 degrees about a line through the middle of the board. That doesn't require a fourth dimension.] It requires one more dimension than that of the object in question. If you include the orientation of the pieces above and below the board, you need a fourth dimension, but not otherwise.
Right, right. But at any rate, it seems to me that this all adds up to what went before: that both rotations and reflections should be considered.

- http://www.dcs.ed.ac.uk/home/mlj/demos/queens/ -- animated display of various solutions (very cool)
- http://www.cs.ualberta.ca/~davidson/SCS/queens/ -- simpler animation of one solution (and simple code)
*[BrokenLink as of 20 Apr 2011]*

This is a job for...EightQueensInManyProgrammingLanguages!

There are 12 unique solutions: http://www.ic-net.or.jp/home/takaken/e/queen/. This includes rotations only; if you include reflections, there are 6. On a physical chessboard, it matters whether the pieces are above or below the board, so a reflection is still "unique".

View edit of April 20, 2011 or FindPage with title or text search