I would like to share some interesting results of playing with the N-Queens Problem solver. The following plots represent distribution of the solutions number depending on the arrangement of a subset of queens. This distribution is built by iterating the possible permutations of such a subset and counting the number of all solutions containing the current permutation (i.e. by solving N-Queens Completion Problem for each permutation).
In this particular case, subset consists of three queens that occupy the first three adjacent columns and only the permutations without overlaps (no one attacks each other) are enumerated. The subset length affects the resolution of the plot but not the general nature of the distribution.
Here you can see results and data for N = 13, 14 ... 17
Top comments (4)
I think it's interesting that this result looks a lot like double-slit light diffraction interference patterns. I wonder if there's a fundamental sinusoidal relationship buried in the N-Queens problem?
Thanks for the reply! Indeed, the pictures a very similar and it seems we can assume the more N the stronger the diffraction-like pattern appearance in the distribution.
It worth noting, that for even values of N there is "dark fringe" in the center, and for the odd values it is "bright fringe". This behaviour at the center is different from the double (or multiple) slit diffraction of the light under the Fraunhofer conditions (there is always the bright fringe at the center). But this is somewhat similar to the Fresnel diffraction in which dark and bright fringes at the center are alternated depending on the slit width.
I think that this periodic pattern can be explained if we assume that to obtain one solution from another we can rotate the board around the center by an arbitrary angle but not just a multiple of 90. The larger N the smaller the minimum angle, rotating by which, we get a different arrangement and possibly a new solution. If all queens are within an imaginary circle inscribed in the square field of the board then after rotation by any angle all queens will be placed on the board. If some queens are outside this imaginary circle, then only rotation by certain angles will place these queens on the board. As a special case, if the queen is located in the corner of the board, then rotation only by angles of a multiple of 90 is allowed. When all three queens (of the subset described above) in current permutation is far from the corner we have bright fringe, if any queen is close to the corner then it is dark fringe. But again, this is just a guess.
Nice observation, the exact same thing came to my mind looking at those pictures.
Some more plots of the distribution. This time I iterated the possible permutations of the subset of three queens that occupy three adjacent central columns.