A bit of fun - nqueens

[dee]

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 other rows or pieces.

Sorry... I'll rephrase. But surely you have to check every position combination of every piece being on the board at the same time?

 

[Edwin]

Silly question probably, but is there a logical progression to the number of possible solutions for each location 0,1,2 etc.?

 

[RobM]

No. You 'mark' the board with scores then total up the result of the squares with pieces on. From that you can determine whether a piece is attacked by any other piece and how many.

 

[RobM]

I'll put together a page with the solutions I mapped (up to 11x11 I think) where I have every possible solution. Maybe you can see a pattern. I could find nothing that linked each location to another location.

 

[RobM]

I just uploaded the excel spreadsheet - it's not nicely formatted for other people as I didn't think anyone else would want to see it
http://domainview.co.uk/queens8solution.xlsx

 

[dee]

Good lord, i'm probably doing your head in here but trying to get this. So each square has a score? Is that weighted? SO for instance.... corners have less chance of being kyboshed as only surrounded by two possible squares and one diagonal?Like wise edge squares have only 5 etc

 

[RobM]

no you overlay arrays.
For example one array covers all the right diagonals. That means you allocate a score of, say 15, going diagonally from top left to bottom right. You allocate 13 doing the same in the squares next to it. 11 the next etc. Another array does the same the other way. Now you only have to total up the array scores that the pieces occupy and, with a bit of maths, you can determine if more than one is on the same line. You don't care which piece, which line, and where from but you have evaluated the whole board in one look. You never have to know where any piece was. You never have to create one for horizontals or verticals because they are never needed. All pieces are created on separate rows. I probably haven't explained that very well
If you want I'll create some images tomorrow to show the programming logic. If nothing else it's an interesting exercise in programming and is faster than anything I've seen around on the net. However I only created this as a tool because I was interested in the actual solutions and wanted to generate them fast. I saw some code that took hours to solve 300x300 and, as you can see from the beginning, my software does it in about 10 seconds or something.

 

[dee]

no you overlay arrays.
For example one array covers all the right diagonals. That means you allocate a score of, say 15, going diagonally from top left to bottom right. You allocate 13 doing the same in the squares next to it. 11 the next etc. Another array does the same the other way. Now you only have to total up the array scores that the pieces occupy and, with a bit of maths, you can determine if more than one is on the same line. You don't care which piece, which line, and where from but you have evaluated the whole board in one look. You never have to know where any piece was. You never have to create one for horizontals or verticals because they are never needed. All pieces are created on separate rows.

aaah....lightbulb. Of course. And all the horizontals are covered by the diagonal arrays so not needed and less checking. I think I get that.

My drunken brain is thinking there must be a way of checking by allocating primes to each square somehow. I am getting my coat now.

 

[RobM]

There's really no need. As long as one diagonal contains all the same values, but different to any other squares not in that diagonal, you only have to see if more than one piece has that value - if so they are on the same diagonal. Once you ascertain how good or bad the position is you swap the first piece with the first piece not on it's diagonal and reevaluate. It solves very quickly as it's either right or wrong but won't (usually) try the same wrong position again and waste time. Occasionally though you get the situation where the current position and the previous position are equally bad. This results in the swapping back and forth of two pieces. I just opt to drop out and try a different start but you could force it to solve with more algorithms - however it's not necessary and in many cases would be slower.

 

[Edwin]

Random musing over toast: would it change the situation if you transform an nxn board into an nn-length line before working on it. In other words, you take each horizontal strip and lay them end to end. Perhaps there are then a series of formulae that could be applied (equivalent to the original geometry of the board) to see if the line is a solution or not.

I should probably stick to toast...

 

[dee]

Random musing over toast: would it change the situation if you transform an nxn board into an nn-length line before working on it. In other words, you take each horizontal strip and lay them end to end. Perhaps there are then a series of formulae that could be applied (equivalent to the original geometry of the board) to see if the line is a solution or not.

I should probably stick to toast...

Wouldnt you still have to find a way of mapping adjacent squares and diagonals along the line though?

 

[Edwin]

Wouldnt you still have to find a way of mapping adjacent squares and diagonals along the line though?

Yes, but maybe the formulae become simpler. I don’t know. They probably don’t.

It was just that I was looking at the back and forth about arrays and array transforms, and I remember how hard that stuff used to seem at school, so I thought “what if it wasn’t an array?” but didn’t really get much beyond that.

 

[RobM]

If you laid them end to end then you would never get a solution because there would always be a piece threatening another piece. A chess board is only a two dimensional array. The thing is if we have to check if the line is a solution or not we have not succeeded in answering the question of whether there is a unifying equation. You end up barking up the wrong tree and simply trying to speed up the manual process of trial and error which we can already do so no need. The algorithm is a simple one and just takes time to compute - we don't want to increase the efficiency we actually don't even want to use the algorithm. It's like trying to improve the efficiency of a wheel when the answer is a jet engine.

Example we'd want something like:
n1+n2+n3+n4+n5+n6+n7+n8=something
where the *only* things that would make this equation correct are the solutions for the board. This would work on any number of n.
Obviously it won't be that simple but I'm sure there is a way of writing the process in equation form. If you come up with that you have proven that the problem doesn't need to be tried, measured, and altered and therefore would get the prize and a place in mathematics history

 

[Edwin]

Ah, not my best Eureka moment then!

Did you see this?
https://www.optaplanner.org/blog/2014/05/12/CheatingOnTheNQueensBenchmark.html

 

[RobM]

Well it would depend on the solution. There is a formula to get ONE solution of any size board to infinity. However I'm not really interested in how fast one can find a solution - there are various code snippets, speed claims etc. As far as I'm concerned we know that they *can* all be solved over time (which will vary from code and algorithm). This doesn't address the issue of actually finding a unifying method and proving it. That is why there isn't a prize offered for solutions of particular boards (even though originally they stated that they wanted to be able to 'fix' certain rows and still come up with a solution which I did and submitted) only for the underlying equation.

 

[RobM]

I also get tired of articles like that which say things like 'The N Queens problem is not NP-complete'. It is. If it wasn't you wouldn't have to check if the solution worked by actually trying it (and changing if it doesn't) - you would know already how to produce ALL working solutions for ANY n. I agree though that it is a terrible benchmark to use for speed testing as individual solutions can be found many different programming ways. Simply put he just hasn't understood the question but he's found a 'quick' way of coming to the conclusion it's 'what is the answer to life, the universe, and everything?' (42 again ) I personally hold more stock in the mathematicians and their understanding of the problem than the lead developer of Optaplanner

 

[Edwin]

More maths, more prizes (more insomnia?)
http://www.independent.co.uk/news/s...million-prize-difficult-amazing-a8119346.html