A bit of fun - nqueens

[RobM]

I'm interested to find out if anyone else shares the 'unhealthy' obsession I have with a unifying mathematical theory for solving any amount of n-queens.

For people who aren't familiar it's a simple problem. You take any size board (with more than 4 pieces) and place the same amount of queens as rows on the board. They cannot check each other. So far there doesn't appear to be any mathematical formula that can state what the positions will be and how many solutions there will be. A prize was offered a while ago to prove that this could not be solved via artificial intelligence or genetic algorithms (although as my video date shows) I have been looking into this for a lot longer. Obviously the only way to do that is to prove that there is a formula which you can use without placing any pieces - hence 'brute force' is not a proof. I was in touch with the uni that offered the prize and had some back and forth interesting emails with them. My conclusion is that it can be solved with genetic algorithms but they are slow (here's one I wrote for visual aid and it 'evolves' to the correct answer but only when there is 'mutation' factor to get it out of a stuck position which is really the same as starting from a different random position.

).

They can be quicker solved with simple algorithms. The reason for this is that there is no 'almost right' answer and the algorithm only evolves to a trial and error situation. You can put down all the pieces and one of them could be wrong or all of them could be wrong but they are all EQUALLY wrong. Therefore there is nothing for an AI to improve.

However using a simple algorithm I came up with this:
https://orderdomain.uk/tmpmath/nqueens.php

That will basically give you an array of rows, and the position on the row the queen needs to be for the solution to work. Note sometimes it fails when it finds that the 'best' position is equally as 'good' as the position before and ends up in an infinite loop of swapping 2 positions back and forth.

I have pages of research and mathematical formulas I've been trying and I would love to hear if anyone else has been approaching this.

 

[RobM]

I'll get me coat.

 

[Systreg]

I don't play chess, how about a game of draughts instead

 

[RobM]

For example a 4x4 board has the formula 3(d-a)+c-b=0 where a,b,c,d are the 4 piece positions. The only two solutions that make this equation (for 4 squares) are a=2,b=0,c=3,d=1 or a=1,b=3,c=0,d=2 which themselves are in fact just *one* solution with the board mirrored. Every solution has a mirror but if it is perfectly symmetrical that will only produce the same positions. I think this is a red herring. I think there has to be a mechanical equation where, providing you place the first piece, everything possible should be derived from that position. At least then you would have, at worst, n equations for n pieces which is massively faster than trying out every position or using a swapping algorithm as I did above.
Maybe I just need some fresh air.

 

[dee]

I'll get me coat.

I read your post and decided not to even bother taking mine off.

 

[dee]

genuine question :

3(d-a)+c-b=0

What do d,a,c & b relate too? Surely a position is a coordinate ?

 

[RobM]

they are the 4 pieces positions on each row
a = piece 1 on row 0 (I start all indexes at 0)
b = piece 2 on row 1, etc
so (2,0,3,1) means row 0, col 2, row1, col 0, row3, col3, row4, col1

this is not really useful as, for example, the equation for 5 pieces is 4(e-a)+(2d-b)=+/-10 where e is now a fifth piece. I gave up on this line of reasoning as, although you could easily deduce the left part of the equation for any amount of pieces, there was no way of determining the right hand side.
On another note there is a way to find the same single solution for ANY amount of pieces up to infinity but this is not a proof as it doesn't determine ALL the solutions for a given board. I did this and submitted it for the prize... very hopeful as deep down I knew that's not what they were asking for The problem is you don't know you've found all the solutions until you've tried every combination *unless* you can either a) figure out a way of determining how many solutions there are for any number of pieces or b) an equation that will produce all solutions.

All solutions have been mapped for up to 26 pieces but this gives you an idea of the lack of correlation or unifying factor:
4x4 - 2 solutions - 1 unique (as it is a 'mirror')
5x5 - 10 solutions - 2 unique
6x6 - 4 solutions - 1 unique
7x7 - 40 solutions - 6 unique
8x8 - 92 solutions - 12 unique
9x9 - 352 solutions - 46 unique
10x10 - 724 solutions - 92 unique
11x11 - 2,680 solutions - 341 unique
26x26 - 22,317,699,616,364,000 solutions - 2,789,712,466,510,280 unique


I wrote software to map all solutions 11x11 takes about 30 secs. However to then go to 12x12 it increases exponentially and takes several minutes. 13x13 was still running a few hours later etc. These figures above have been brute force mapped - ie EVERY combination is tried. That is a lot for a 26x26 board My software doesn't try every combination it throws down a random start, solves it, and stores the solutions but this only relies on me already knowing how many solutions there are already up to 26x26 so I know when to stop. I was only interested in seeing all the solutions and seeing if I could find a link between them.

For example here are all the solutions for 8x8:
[0] => 0,4,7,5,2,6,1,3,
[1] => 0,5,7,2,6,3,1,4,
[2] => 0,6,3,5,7,1,4,2,
[3] => 0,6,4,7,1,3,5,2,
[4] => 1,3,5,7,2,0,6,4,
[5] => 1,4,6,0,2,7,5,3,
[6] => 1,4,6,3,0,7,5,2,
[7] => 1,5,0,6,3,7,2,4,
[8] => 1,5,7,2,0,3,6,4,
[9] => 1,6,2,5,7,4,0,3,
[10] => 1,6,4,7,0,3,5,2,
[11] => 1,7,5,0,2,4,6,3,
[12] => 2,0,6,4,7,1,3,5,
[13] => 2,4,1,7,0,6,3,5,
[14] => 2,4,1,7,5,3,6,0,
[15] => 2,4,6,0,3,1,7,5,
[16] => 2,4,7,3,0,6,1,5,
[17] => 2,5,1,4,7,0,6,3,
[18] => 2,5,1,6,0,3,7,4,
[19] => 2,5,1,6,4,0,7,3,
[20] => 2,5,3,0,7,4,6,1,
[21] => 2,5,3,1,7,4,6,0,
[22] => 2,5,7,0,3,6,4,1,
[23] => 2,5,7,0,4,6,1,3,
[24] => 2,5,7,1,3,0,6,4,
[25] => 2,6,1,7,4,0,3,5,
[26] => 2,6,1,7,5,3,0,4,
[27] => 2,7,3,6,0,5,1,4,
[28] => 3,0,4,7,1,6,2,5,
[29] => 3,0,4,7,5,2,6,1,
[30] => 3,1,4,7,5,0,2,6,
[31] => 3,1,6,2,5,7,0,4,
[32] => 3,1,6,2,5,7,4,0,
[33] => 3,1,6,4,0,7,5,2,
[34] => 3,1,7,4,6,0,2,5,
[35] => 3,1,7,5,0,2,4,6,
[36] => 3,5,0,4,1,7,2,6,
[37] => 3,5,7,1,6,0,2,4,
[38] => 3,5,7,2,0,6,4,1,
[39] => 3,6,0,7,4,1,5,2,
[40] => 3,6,2,7,1,4,0,5,
[41] => 3,6,4,1,5,0,2,7,
[42] => 3,6,4,2,0,5,7,1,
[43] => 3,7,0,2,5,1,6,4,
[44] => 3,7,0,4,6,1,5,2,
[45] => 3,7,4,2,0,6,1,5,
[46] => 4,0,3,5,7,1,6,2,
[47] => 4,0,7,3,1,6,2,5,
[48] => 4,0,7,5,2,6,1,3,
[49] => 4,1,3,5,7,2,0,6,
[50] => 4,1,3,6,2,7,5,0,
[51] => 4,1,5,0,6,3,7,2,
[52] => 4,1,7,0,3,6,2,5,
[53] => 4,2,0,5,7,1,3,6,
[54] => 4,2,0,6,1,7,5,3,
[55] => 4,2,7,3,6,0,5,1,
[56] => 4,6,0,2,7,5,3,1,
[57] => 4,6,0,3,1,7,5,2,
[58] => 4,6,1,3,7,0,2,5,
[59] => 4,6,1,5,2,0,3,7,
[60] => 4,6,1,5,2,0,7,3,
[61] => 4,6,3,0,2,7,5,1,
[62] => 4,7,3,0,2,5,1,6,
[63] => 4,7,3,0,6,1,5,2,
[64] => 5,0,4,1,7,2,6,3,
[65] => 5,1,6,0,2,4,7,3,
[66] => 5,1,6,0,3,7,4,2,
[67] => 5,2,0,6,4,7,1,3,
[68] => 5,2,0,7,3,1,6,4,
[69] => 5,2,0,7,4,1,3,6,
[70] => 5,2,4,6,0,3,1,7,
[71] => 5,2,4,7,0,3,1,6,
[72] => 5,2,6,1,3,7,0,4,
[73] => 5,2,6,1,7,4,0,3,
[74] => 5,2,6,3,0,7,1,4,
[75] => 5,3,0,4,7,1,6,2,
[76] => 5,3,1,7,4,6,0,2,
[77] => 5,3,6,0,2,4,1,7,
[78] => 5,3,6,0,7,1,4,2,
[79] => 5,7,1,3,0,6,4,2,
[80] => 6,0,2,7,5,3,1,4,
[81] => 6,1,3,0,7,4,2,5,
[82] => 6,1,5,2,0,3,7,4,
[83] => 6,2,0,5,7,4,1,3,
[84] => 6,2,7,1,4,0,5,3,
[85] => 6,3,1,4,7,0,2,5,
[86] => 6,3,1,7,5,0,2,4,
[87] => 6,4,2,0,5,7,1,3,
[88] => 7,1,3,0,6,4,2,5,
[89] => 7,1,4,2,0,6,3,5,
[90] => 7,2,0,5,1,4,6,3,
[91] => 7,3,0,2,5,1,6,4,

 

[RobM]

See notice in the 8x8 solutions:
[0] => 0,4,7,5,2,6,1,3,
[1] => 0,5,7,2,6,3,1,4,
[2] => 0,6,3,5,7,1,4,2,
[3] => 0,6,4,7,1,3,5,2,

That means there are NO solutions for a piece on row 0, col 0 and the next on row 1, col 2 or 3 or 7. Why? It's frustrating because until all the pieces are down you can't determine if it works. So if you try it with a real board and put those 2 pieces down like I stated you will never be able to make it work for the other 6 pieces. You are dead in the water.

 

[Admin]

Rob....try not to think.

 

[RobM]

lol I wish I could turn it off. You know I sleep about 4 hours per night because of appalling insomnia - just look at my post dates? The brain never stops although I often wish it would

 

[dee]

lol I wish I could turn it off. You know I sleep about 4 hours per night because of appalling insomnia - just look at my post dates? The brain never stops although I often wish it would

you should take up chess.

 

[cc976a]

What's the reason for the drop in solutions between 4x4 and 5x5 when all other increases in board size increments the number of solutions?

I haven't got a 6x6 chess board to sit and work it out

 

[RobM]

Exactly
There is an equation I worked out (but can't find off hand) which shows why there will only be one solution for a 6x6 - I'll find it later. That was the only thing I could prove mathematically. Unfortunately it cannot be linked to any other size boards.

Solution is:
[0] => 1,3,5,0,2,4,
[1] => 2,5,1,4,0,3,
[2] => 3,0,4,1,5,2,
[3] => 4,2,0,5,3,1,

Note these are all just one solution with the board rotated or mirrored

 

[RobM]

It's to do with transforms - these are what I worked out to rotate 90 degrees a setup


t=square, k=pieces

Where t goes from 0 to (k squared)-1 so 6x6 board is 0-35
t => (k-1)-(int)t/k + k(t mod k)
eg on a 6x6 board a piece at top left (square 0) maps onto square 5 then square 35 then square 30 then back to square 0

or in 2 dimensional coordinates which can be easier for some things
x,y => k-y-1, x

 

[dee]

It that effectively mathematically checking line of site ?

 

[RobM]

I'm not sure what you mean.

 

[dee]

Just wondering on the approach to the solution. Maybe I've got the gist wrong. I would have thought you start at t=0 , check horizontal and vertical row for pieces, then diagonals . If nothing sight, a piece down, move on to next square.

Or am I miles off.

 

[RobM]

There is no issue with actually solving it. My software simply swaps rows to get the best result until it's solved. The issue is with coming up with an equation that can be applied to any amount of pieces and will determine all the successful outcomes without resorting to trial and error or brute force.

 

[RobM]

eg if you place a piece, n, at the top left of the board on an 8x8 we know that n+1...8 cannot be used again. Also n+8, n+16, n+24 etc Also n+9, n+18, etc
Now once that piece is placed the next piece's equation will combine with that. We want an overall equation that will produce all solutions for any size board.... if one exists.

 

[dee]

Yep.... good job i kept my coat on.