display | more...
One of the more famous chess puzzles, the eight queens puzzle asks that the solver place eight queens on a chess board in such a way that none of them is under attack from any of the others. Excluding rotations and reflections, there are twelve different ways to do this.

Writing an efficient algorithm to solve the problem is an instructive exercise undertaken in many computer science courses, since it builds understanding of recursion and backtracking. Here's a rough sketch of a very bad algorithm which produces many duplicate answers, but illustrates the general idea:

	if no captures possible then
		if numqueens = 8 then
			output solution
			for each unoccupied square 
				place queen on square
				remove queen

The puzzle generalises easily to other square boards, the 4x4 board being the smallest on which a solution exists.

There is a simple algorithm yielding a single solution to the n queens puzzle for n = 1 or any n ≥ 4. It wasn't the first simple one ever created, but it does work :

  1. Divide n by 12. Remember the remainder (it's 8 for the eight queens puzzle).
  2. Write a list of the even numbers from 2 to n in order.
  3. If the remainder is 3 or 9, move 2 to the end of the list.
  4. Write the odd numbers from 1 to n in order, but, if the remainder is 8, switch pairs (i.e. 3, 1, 7, 5, 11, 9, …).
  5. If the remainder is 2, switch the places of 1 and 3, then move 5 to the end of the list.
  6. If the remainder is 3 or 9, move 1 and 3 to the end of the list.
  7. Place the first-column queen in the row with the first number in the list, place the second-column queen in the row with the second number in the list, etc.

Examples :

  • 8 queens (remainder 8): 2, 4, 6, 8, 3, 1, 7, 5.
  • 14 queens (remainder 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
  • 15 queens (remainder 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
  • 20 queens (remainder 8): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 5, 11, 9, 15, 13, 19, 17.
Note to those, for some reason, checking: I submitted this algorithm to Wikipedia.

Also, the problem is effectively the same as (isomorphic to) the problem of choosing a permutation of the first n naturals such that the distance between any two elements is not the normal distance (for instance, you wouldn't have …1, 5, 3… or …3, 25, 1… because 1 and 3 are normally two apart).

It is impossible to have two queens sharing the same column or row. If rows are represented by the actual permutation numbers, they each occur only once. If columns are represented by the permutation positions, they can only occur once.

It is impossible to have two queens sharing the same diagonal. For every permutation position (column) a bishop moves, it must move one permutation number (row), so the position and the number must change by the same absolute value. If two squares do not share their normal distance, the change in absolute value of the two values is different and this does not happen.

Therefore, the two are the same problem. Thinking of it as a permutation with no normal distances is usually simpler than thinking of it as queens on a chessboard.

Log in or register to write something here or to contact authors.