1218. Queens, Counted Up to the Mirror

Place n queens on an n by n board so that no two share a row, a column or a diagonal. Two placements that are left-right mirror images of each other count as the same placement. Report how many different placements there are.

n = 6 -> 2 the four arrangements fall into two mirror pairs n = 4 -> 1 the two arrangements are mirror images n = 3 -> 0 there is no arrangement at all n = 1 -> 1

Problem #1176 prints every arrangement and #1183 counts them. This counts them up to the mirror, and the saving is the point: the search can be cut almost in half before it starts.

## What most people try first

Enumerate every arrangement, as #1176 does, then group them into mirror pairs and count the groups. That works and it does all the work it was trying to avoid, plus the grouping. At n = 10 it builds 724 arrangements to report 362.

## The symmetry break

The mirror sends the queen in column c to column n - 1 - c. So the natural rule is: force the queen in the FIRST ROW into the left half of the board, that is into a column below n / 2. Mirroring an arrangement whose first-row queen is in the left half puts it in the right half and vice versa, so exactly one of each mirror pair survives.

That halves the search and for even n it is the whole answer.

## Where that rule is not enough, which is the point of this problem

For ODD n there is a middle column, (n-1)/2, and it is its own mirror image. An arrangement with its first-row queen in the middle column mirrors to another arrangement whose first-row queen is ALSO in the middle column. The left-half rule does not separate those two, so both survive and the pair is counted twice. Unless the arrangement happens to be its own mirror image, in which case there is only one of it and counting it once is right.

So a second rule is needed, and only for that case: among arrangements whose first-row queen is in the middle column, keep only those that are at most their own mirror image, comparing the column sequences position by position.

at a complete arrangement: if n is odd and the first-row queen is in the middle column: if the column sequence is greater than its mirror: reject count it

Leaving that out is the characteristic bug, and it is quiet: the answer is right for every even n and too large for odd n with a solution, which is n = 5, 7, 9 here. Those three are in the tests.

## The independent check, which is worth knowing as a technique

Burnside's lemma gives the number of orbits of a group acting on a set as the average number of elements each group element leaves fixed. The group here has two members, the identity and the mirror, so

orbits = (arrangements fixed by the identity + arrangements fixed by the mirror) / 2 = (total + mirror-symmetric) / 2

Every arrangement is fixed by the identity, so the first term is the plain count. The second is the number of arrangements equal to their own mirror image. That formula is computed from the full enumeration as a check on the pruned search, and it is a genuine second opinion rather than a rerun: it never considers the left half of the board at all.

## The settled boundaries

n = 1 has one arrangement and it is its own mirror, so the answer is 1. n = 2 and n = 3 have no arrangement at all, so the answer is 0 and the output is a count rather than the word none. n = 4 has two arrangements forming one mirror pair. All four are tested, and the first odd case with a solution is n = 5.

## Cost

One node per partial placement with the first-row queen in the left half, which is a little under half of the unrestricted tree, plus O(n) at each odd-n middle-column leaf for the mirror comparison. The counting is still exponential, as it must be.

Constraints - `1 ≤ n ≤ 10`