Eight Queens Problem

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).

• 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!

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.