DEV Community

Discussion on: Solutions Distribution of the N-Queens Problem

Collapse
 
rpalo profile image
Ryan Palo

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?

Interference pattern reference

Collapse
 
zubetto profile image
Alexander

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.

Collapse
 
lucretius profile image
Robert Lippens

Nice observation, the exact same thing came to my mind looking at those pictures.