The queen's necklace

A real necklace of many beads.

The title of this page should be a tiny joke: this page deals with mathe­matical necklaces, of course, and with their relation to the n queens problem.

What is a mathematical necklace?

Obviously, mathematicians look at real necklaces super­ficially. A necklace consists of parts held on a string. The parts are mostly beads, but can also be some fine piece of metal or wood.

A real necklace has a lock which is a natural point to start if you will enumerate the parts in detail. On the contrary, a mathe­matical necklace has no lock, no starting point. Wher­ever you start, it is considered as the same necklace. All parts of a mathe­matical necklace are beads, and all beads look the same, with exception of their color. So, only the number of beads and the sequence of their colors is important. In addition, you can turn over a mathe­matical necklace, and it remains the same object.

This was the terminology some years ago, as far as I knew. Meanwhile, mathematicians had a closer look to the necklace, as I found from Wikipedia: you are no loger allowed to turn over the necklace; corresponding objects which you can turn over are called bracelet today. As an alternative, one can speak of free and fixed necklaces. In these pages, I use the old terminology, i.e. necklaces are always free (or are bracelets), it will take some time until all is converted to new terminology.

In mathematical terms, we start form a finite sequence of colors, and define a necklace a equivalence classes of such sequences under rotation and reflection. Reflection is in this case simply the inversion of a sequence, reading it backwards. Another, equivalent definition is: a necklace is a orbit of finite sequences of colors, under action of the dihedral group.

Similarity of necklaces

For the n-queens problem (see below), I do not use the usual (mathematical) necklaces; instead, I use equivalence classes with regard to extension. The number of beads corresponds to the size of the board, i.e. the number of cells in a row or column. While the distiction of bracelet and necklace eliminates a transformation, the step to similarity adds transformations. An extension is possible without problems (i.e. bijective), if and only if the extension factor and the size of board (= numer of beads) are relatively prime.

We also introduce an ordering for the equivalence classes under similarity. The first rule is that necklaces having less black beads are smaller than those having more black beads. If the number of black beads is equal, then order is derived from the "alphbetic order". But for that, one has to choose the smallest element in the equivalence class first.

Some pictures shall give examples for the equivalence classes. You can see them in full size if you click on them. The "black beads" are red beads in the picture.

Size	Number of black (or red) beads
11	All equivalence classes in one image:
35	3	6	7
35

Relation to the n queens problem

Somehow, necklaces are the one dimensional cor­respondence to a torus chess board or to the torus n-queens problem.

You can divide the fields of a n by n chess­board into lines of length n. For instance, you can do it by the horizontal lines, the rows. You can use the columns, the vertical lines, as well. Similarly, you can take the diagonals and anti­diagonals (diagonals to the right and to the left). They would be partly shorter on a bounded board, but on a torus board of n by n cells, they have all length n as desired. We get a necklace of black and white beads, if we assign a white bead to empty cell of a line, and a black bead to a cell occupied by a queen.

These necklaces are of limited interest. For rows and columns, the same necklace results from every line. One bead is black, all others being white. That is the same for diagonals, if we handle torus solutions. There are some variations if we handle solutions of the regular n queens, from the torus perspective: there may be two queens on the same line, or no at all.

There are other partitions of lines for the chess board. We can use knight lines, for instance. You get a knight line if you always move one line up and two columns to the right.

Queens on a knight line; a torus solution for n = 13.

Basically, you can use all partitions of the boards cells, consisting of subsets of n cells. You must enumerate the subsets, define a cyclic order within each subset. By that, you get a sequence of necklaces from every pattern of queens on the chessboard. However, that is so general, that I cannot see any use of it.

Meaningful and sufficient general is it to take partitions that arise from the partition of horizontal lines by bijective affine mappings.

Such lines can lead to almost all black and white necklaces. If n is odd and not divisible by 3, then you get a torus solution by selecting a completely black necklace for one knight line, and completely white necklaces for all parallel lines. That is, the queens stand precisely in a knight line, as shown in the picture.

Application in the n queens problem

You can arrange the sets of solutions along with necklaces on diagonals and antidiagonals. For that, you take these 2n lines, get a necklace for each, and then take the maximum. You use the fact that a congruent mapping does neither change the maximal necklace nor the number of any necklace appearing within the set of necklaces.

The maximal necklace for diagonals has either one or two black beads. A necklace of two black beads corresponds to a conflict of two queens seen only on the torus (see page "Conflicts").

If the maximal necklace of a n queen configuration has only one black bead, then the configuration is a torus solution. In this case, it makes sense to go to the next step.

For that, we arrange the solutions along with their necklaces on the knight lines. There are four types of knight lines: up or down, and steep or flat. The maximum is taken under these 4n lines.

On that, I do not use the usual mathematical necklaces; I use instead equivalence classes of them, under expansion. An expansion may be done without problems (i.e. as an invertible mapping) if the expansion factor is relatively prime to the size of the board.

You can introduce an order on these equivalence classes. For instance, you can define that necklaces having less black beads are smaller than necklaces having more black beads. If the number of black beads is equal, the alfabetic order will decide. For doing so, you have to represent every equivalence class by its lowest member.

These equivalence classes fit exactly to actions of the group of similar trans­formations on the chess board. Doing the search, you go through the equivalence classes one by one. You set queens on one knight line according to the black beads. Then, you fill with more queens, according to the torus rules. The key point in the filling and search is that you can exclude all cells that would lead to a bigger necklace.

Doing so, you start with only few queens. Then, the exclusion of cells has a strong effect, and you get all possible extensions relatively fast. Coming to necklaces containing more black beads, the search space will become larger. Finally, you handle necklaces containing many black beads; then, the number of queens already on the board reduces the search space.