n queen topics
Home
Group actions
Search algorithm
Use symmetry, regular NQ problem
Special properties
Necklaces
Conflicts
Conflict tables
Smallest solutions and greedy sequence
World records
Tables of counting results
Images for n=8
Torus images for n=13
Other pages to the n queens problem
Bibliografy
 
 
Other themes
Primes from sums of factors
Primes from wrong binomic formula
Numbers by primes distribution
 
 
 
This page in another language
German

Evolution trees

Relationship by group actions

The relation of different solutions to the n-queens problem can be shown like a evolution tree in biology, or in other words, a pedigree tree of the species. The group actions of different groups correspond to evolution lines.

The author has written an article explaining this for the classic case n = 8. It has been published in Spektrum der Wissenschaft in August, 2010 (in German; I do not know whether a professional translation to English exists. If you are inerested in my own translation, mail to me).

On this page, you find some of these pedigrees, for various board sizes. They are created by the same scheme, and the following legend (= symbol explanation) applies to all of them. The images are created as SVG files; should they appear too small for you, then you can show the images larger easily, by right clicking "Show graphic"; and you come back here by Alt + <-.

The representation of the arrows should remind of the type of movement. For the general affine transformations, the arrow is made of small squares that are sheered laterally, in everyday language. Expressed mathematically, the squares have been transformed by a shear transformation. Shear transformations are the simplest type of affine transformations which go beyond central dilations and congruent movements. The matrix for the mapping and the vector for the subsequent shift are indicated above the arrow. Under the arrow is the numbering of the affine germ, starting with a capital A.

It happens that one affine germ leads to different solutions which are not similar to each other; "similar" means "central dilations and congruent movements" here. In this case, a vertical arrow is shown from the affine germ to the similarity germ of the next solutions.

The arrow of a central dilation should remind of a polygraph. This mechanism is also used for an extension arm of an adjustable wall-mounted shaving mirror; a fine picture of it, with animation, is found in the English Wikipedia; search for "Pantograph mirror" on this page. The dilation factor k is given as "by k" above the arrow. The starting point is always the similarity germ, not the previous stretched figure.

It happens that dilations of different factors lead to congruent solutions. In this case, the other factors are written over the similarity germ, with text "also for ...".

The association for shift-arrow is that the arrow is made up of red building blocks, and each other is shifted. Near the arrow, the shift vector is shown.

The blue double arrow for reflection, and the green round arrow for the rotations need no further explanation, I hope.

Small boards

The smallest solution tree is for n = 4. In the affine germ, the queens are arranged compactly in a small square.

For n = 5, the queens in the affine germ form a single row. There is always such a very simple solution, when n is neither divisible by 2 nor by 3; then, it is also a solution to the torus problem.

For the first time, solutions arise from shift operations, beyond the dihedral group.

Another peculiarity of n = 5 is that all solutions of the normal queens problem are solutions of the torus problem also. This happens never again.

For n = 6, there are fewer solutions than for n = 5; the main reason is that the regular solutions no longer are possible.

Again, the queens in the affine germ stay compactly, in a 2 × 3 rectangle.

For n = 7, the image becomes larger: there are several affine germs, for the first time, and thus different background colors for the grouplets of solutions.

There is a very simple solution, as for n=5, where the queens in the affine germ form a single row.

For the first time there is also the case that a dilation leads to a dead end: there is no shift such that all conflicts are resolved.

The classical case n=8 which is discussed in the article mentioned above.

There are 4 affine germs which lead to 6 germs for similarity. A dead end appears twice.

A large number of solutions (56) stem from the same congruency germ. Together with the extension, the nuber is 64, or more than two thirds of the total number! The reason is that there are only 2 conflicts in this branch (see "Conflicts"), while the other branches have 4 conflicts. The higher the number of conflicts, the less solutions in the branch.

Medium size: the 9 by 9 board

If you build the family tree for n = 9 by the exact same rules, then the image is very elongated. Therefore, it is divided here into 3 parts.

Altogether, there are 10 affine germs; the germ A4 is particularly fertile and produces the largest image (below) alone, with 232 of the 352 solutions. In the first image (right), 4 germs generate 48 solutions, and in the third image (bottom right) 5 germs lead to 72 solutions.

Germ A3 is intresting, as the queens stay compactly in a 3 by 3 square.

Larger boards

You can not create such images for any size of boards, for the number of solutions is growing too fast. But with a few simplifications, we can go a bit beyond n=9. I will include such images here in the future.

Other relationships

In addition to the algebraic relationship, which is produced by group-effects, one can think of other relationships. On the one hand, it is about solutions of different sizes. For example, you get a (n-1) solution from a n-solution in which a queen stands on a corner cell, if you take away the corresponding row and column. On the other hand, there are pairs of solutions where most queens are on the same cell, only few have changed their place; this can be regarded as a mutation, to stay in the language of biology.

When I know more about it, I will insert it here.

Start of page
Prepared by Matthias Engelhardt
Mail to Matthias Engelhardt
 
last change: 2015-09-08
Address of page: http://nqueens.de/sub/EvolutTree.en.html