How many different positions can 8 queens be placed on a board without them threatening each other?

How many different positions can 8 queens be placed on a board without them threatening each other?

Fire post)

You can wiki it. It's something like 12 positions when you don't count count rotations as unique positions.

92

Now write an optimal algorithm to find the solution to this problem for any board size.

An interesting question and I think I've heard of it before ... well, I would guess it is a multiple of 8 because if you find a solution, you can flip the board horizontally, or vertically as well as rotate it 90 degrees and those solutions would also still be valid.  Each of those options has 2 choices and there are 3 of them, so 2*2*2=8 ... so, if there is at least 1, then there are at least 8.

Now a question might be whether or not any of those transformations of the board could result in redundant and identical solutions, but I would suggest not, because if queens can threaten each other then flipping or rotating the board in these manners would not alter that.

If you consider that queens can move horizontally or vertically along their ranks or files, then valid solutions would require only one queen be on each rank or file (horizontal row or vertical column).

... and then additionally, no two queens could share the same diagonal ... yeah, I'm certain it could get a bit confusing there and there are probably only a limited number of permutations possible, so ... best wishes and good luck on figuring it out!!

It could be interesting to explore what other transformations to their placements might also guarantee valid solutions ... for example, swapping rows, columns or diagonals.

That is an NP-Complete problem.  If you can find a solution that is not a brute-force solution, you will have solved all NP problems.  In short, likely not possible with current computing capabilities.  Possibly done with quantum computing (at least that is the hypothesis).

Interesting thought here, in fact I think this question might be related to many complex fractal and chaotic images generated by computer graphics because some of the processes are similar.

The basic premise is if you can find an optimal solution for one NP-Complete problem, you can find one for all of them.  Thus, if you could do that, you would almost be guaranteed a Nobel Prize in Mathematics.

Thanks much for sharing that info 🙏 ... in fact discovering how that that statement might be true seems like quite and interesting challenge, in itself.  I don't know how that was derived, but yes, maybe there is some sense in which all NP-Complete problems are comparable on infinite scales of computational power. 

.... oh dang, you actually inspired me to think a bit more about this and here is a a 'flip-side'/alternate (and potentially crazy and insane) view of things that "All 'real world' problems are (at least potentially) NP-Complete" ....

I remember there being some (as far as I know, still unsolved) "Millenium Problems" https://www.claymath.org/millennium-problems and for at least one of them - the "Navier-Stokes" equations, I have 'solved' it sufficiently well to be happy with the results ... the equations are not describing how fluids move in life or the "real world", but instead attempting to describe how idealized mental assumptions about such fluids might behave in "real life" ... or at least that is my impression.

On the flip side of this, by trying to analyze the boundary conditions of this 'dilemma' and the apparent paradoxes involved and trying to 'map' some of the characteristics of the divergences between these idealized views and the properties of things I would consider to be more real and able to be expressed in ways that are more finite and tangible ... well, it actually got rather spooky more than once with some of the images that came rather naturally out of the math / logic behind them and I ended up putting it all aside for years to try to better understand what the experiences were trying to express to me ...

Overall, the conclusion that seems most likely true is more or less that 'Anything is possible'.

Yep, interesting stuff.  Well, I wish you the best, 'PawnTsunami' and maybe we'll meet up again in one form or another.

Best wishes and hope your week goes well.