A bit of fun - nqueens

[RobM]

Think of it this way. If I give you a board and 8 pieces you will solve it by putting the pieces down and adjusting them until it works. Now imagine you could only put the pieces down once and simultaneously - the chances of it not being right are far higher than it being correct. However with a working mathematical equation you could theoretically work out in *ONE* equation where all the pieces would have to be placed for it to work. But to make it more annoying we know there are multiple correct answers - the equation would have to apply to all of them. This equation has not been found (and may not exist). This is the question that hasn't been answered for decades. Bear in mind though that in maths problems can exist for decades but still have a solution (look up Fermat's last theorem) for an example - he theorised something in 1637 and it wasn't proved until 1995). I am in the camp that thinks there must be a single unifying equation as it is mechanical to arrive at *a* solution but not know how many others there are or know the solution before it is found.

A bit of fun https://orderdomain.uk/tmpmath.php - the squares grey off as you place a piece to show you where you can't put another piece. Even with that it can be very difficult for large boards (eg 20)

 

[Edwin]

I wonder if you could train some kind of AI expert system with lists of answers for boards of different sizes, and see if it could derive a rule (effectively a formula) from “studying” all the correct positions?

I say that having glanced gingerly at the tougher parts of this thread and then shied away at the complexity, so it could be a nonsensical suggestion.

 

[RobM]

Not nonsensical at all that is exactly what AI should be used for. We have trillions of solutions I'm sure a neural network could be trained by far more intelligent people than me - my experience with neural networks and matlab on a few thousand solutions came up with nothing. Instead of prizes being offered to solve the problem using AI maybe AI should be used to find the link (thinking of 42 now - we don't know what the question is). Maybe it has already been tried and there simply isn't a pattern, there is no equation, and it can't even be thought of in mathematical terms - a bit like trying to mathematically prove what chicken tastes like. I must admit it galls me a lot that I'm going to die not knowing the answer (if there is one). At least when quantum computers become commonplace we can map the solutions for far higher pieces as they'll be able to try every combination at once. However whilst working for so long, filling notepads, and writing algorithms my wife asked me a simple question 'does it matter?' lol

 

[dee]

What I can never fathom in these situations is that the equation has to relate to a sense of space, and multiple outcomes existing at the same time. How does it know! First thing I thought of was quantum computing, but then that in itself does my nut in.

 

[RobM]

Well lots of equations can produce more than one result.
x=√9 for example has two results - only two numbers will make it true.
So if there is a unifying equation there will be finite amount of results (that may vary on board size) produced by it.
So for example as I showed above if we take the 4x4 board there are only two sets of data that will make the equation 3(d-a)+c-b=0 true for whole values 0 to 3 with each value used only once. Those two sets are the solutions. However we only know there are 2 sets of results because we have tried every combination and found what works. So really I have worked backwards from knowing the amount of results to fitting an equation that works to it - a total red herring really.

The place to start really is first finding out a way of calculating how many solutions an n x n board will have. That however has to be proven or you'd have no way of knowing if there was values you hadn't tried where it didn't work. An equation isn't proof but it's a good starting point to create the proof. A bit like the recurring numbers of pi - in the past we assumed they could not repeat even though we had mapped them to ridiculous amounts but it was only *proven* because it is an irrational number. Otherwise we'd be left wondering if there were more digits where it would repeat.

 

[dee]

Completely understand the concept ( ie 3 & -3 satisfy x=√9 ) And studied maths to a reasonably high level by general standards. Trouble is I had to work at it. I could never "see" it. It was always hard work for me. Its like music I think. You have or you don't. I can see music, and find it frustrating I can't see maths. You obviously do it for fun !

 

[Edwin]

If Google's AlphaZero becomes available on a software as a service basis, perhaps you could try using that to hammer away at the puzzle. After all, it learned to play Chess and Go from first principles, and became the undisputed master of both games within a remarkably short space of time - so if there IS an answer I would expect it to be able to find it...

 

[RobM]

I wish I was better at it. I envy people that can read it like a language. I did it at University along with physics and (then new) business computing in the 90s. I was mediocre at best and never really 'got it'.

 

[RobM]

Yes I was watching a few videos of it playing stockfish with analysis on yt. I didn't really even understand the logic of the analysis lol

 

[Edwin]

A few bits of reading you've almost certainly already seen (may, perhaps, interest others?). All three are closely related but complementary.
https://www.st-andrews.ac.uk/news/archive/2017/title,1539813,en.php
https://blogs.cs.st-andrews.ac.uk/csblog/2017/08/31/n-queens-completion-is-np-complete/
http://www.claymath.org/events/news/8-queens-puzzle

 

[RobM]

Yes I was corresponding with someone at st Andrews after I realised I had already been looking into the question they were offering a prize for. I think it was Professor Gent or someone. They had to clarify the question because I, like hundreds of others, submitted an algorithm that could produce a solution for an infinite size board. I think they were fed up with our low level of understanding lol.

 

[Edwin]

Oh, and this, which I quarter-understand in the most tenuous way (not false modesty, sadly the unvarnished truth...)
http://johncorni.sh/snippets/2017/11/27/concise-haskell-nqueens.html

 

[Edwin]

Yes I was corresponding with someone at st Andrews when I realised I had already been looking into the question they were offering a prize for. I think it was Professor Gent or someone.

The third of my posted links implied there was some media confusion about exactly what problem the prize was to be given for.

 

[RobM]

I remember thinking it was a bit odd how they phrased it to start with. It implied they wanted solutions that could be achieved fast or via genetic algorithms. Of course they don't want any such thing they just want a proof that either it can't be done mechanically and/or that it can be done via AI. I think that's a little unfair myself because a mechanical proof would immediately prove that you *don't* need AI or an evolution of the solution but I guess that's why it's still unclaimed With regards to the algorithm they don't want it is simply a case of placing the pieces randomly - evaluating, looping through each row and swapping best values until you have either succeeded or can't improve that position. That's what my software linked at the beginning does. I was more interested in mapping the solutions and finding a unifying equation.

 

[dee]

I wish I was better at it. I envy people that can read it like a language.

I know what you mean. I had a friend at school (although haven't seen him in years) who could "see" it, and I mean at a serious gifted level.Constantly had people shuffling around him from aged about 15. Had NASA courting him amongst others while he was still a teenager in our Hicksville village in Fife. All he wanted to do was work on a farm and drive tractors.He went and got all his qualifications and did some amazing work in lasers I think, but ultimately he now drives tractors and loves it.

 

[dee]

Yes I was corresponding with someone at st Andrews when I realised I had already been looking into the question they were offering a prize for. I think it was Professor Gent or someone.

Spent my formative teenage drinking years in St Andrews . Which is probably why i'm rubbish at maths now.

 

[RobM]

Basically they said at the beginning they wanted a way that didn't use backtracking or brute force. Then they changed it to a proof of non-existence (impossible unless you can prove there is one). They stopped talking about AI I guess as even without proof it's pretty obvious that there is no best fit solution to evolve to in a right/wrong problem. As Edwin said I think AI would be suited to find the existence of a polynomial time algorithm and I still cling to the belief (note belief) that there is one. I hate belief - I demand proof

 

[RobM]

Oh, and this, which I quarter-understand in the most tenuous way (not false modesty, sadly the unvarnished truth...)
http://johncorni.sh/snippets/2017/11/27/concise-haskell-nqueens.html

His method is a very slow way of doing it Overlaying an array of diagonals already scored means you only have to pass once not x times. He's fallen into the trap of looking at it piece after piece - it needs to be taken as a whole single placement in my opinion for programming speed. I evaluate by placing all the pieces then checking the value they are 'on'. You can deduce immediately whether any others are checking it without having to check where from or 'pairing queens'. But anyway this is pointless - the task is not to improve the speed of the process - the task is to find a single way of producing all the outcomes without any testing.

 

[dee]

I evaluate by placing all the pieces then checking the value they are 'on'. You can deduce immediately whether any others are checking it without having to check where from.

Excuse my ignorance, but does that mean you have to check every possible placement, as you'll never know every possibility unless you try them all ?

 

[RobM]

I mean you can place all the pieces on the board at once and know in one overall look if any are being threatened by any others without having to check any rows or pieces. However speeding up the process is not really the point - even if quantum computers do a million pieces in a millisecond it still means nothing if they had to use trial and error to get each solution.