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 :
- Divide n by 12. Remember the remainder (it's 8 for the eight queens puzzle).
- Write a list of the even numbers from 2 to n in order.
- If the remainder is 3 or 9, move 2 to the end of the list.
- 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, …).
- If the remainder is 2, switch the places of 1 and 3, then move 5 to the end of the list.
- If the remainder is 3 or 9, move 1 and 3 to the end of the list.
- 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.