|
|
This can't be real, there is a well known linear-time algorithm. It's even on wikipedia!
E: in the actual paper it is clear that what they did here is prove that a specific variant (where some queens are pre-placed) is NP-complete, so you get the prize by solving the P?=NP question.
modified 1-Sep-17 17:48pm.
|
|
|
|
|
Well,
It would take thousands of years to solve the problem on really huge grids... say 2500x2500 The whole point of the challenge is to come up with a new faster method for solving the problem.
It also takes a lot of RAM... my depth-first implementation runs out of memory on really huge grids somewhere above 900x900. I didn't spend any time optimizing so I could probably fix this with file-backed memory.
Best Wishes,
-David Delaune
|
|
|
|
|
It's already linear time, what more do you want?
Wikipedia wrote: If the goal is to find a single solution then explicit solutions exist for all n ≥ 4, requiring no combinatorial search whatsoever.
.. some formulas to calculate the placement follow, all of them trivial arithmetic.
|
|
|
|
|
Mine doesn't chew up memory as it works; it allocates all it needs at the beginning and then just uses it. As n increases, it doesn't complete in a usable amount of time of course. I don't know whether or not I let it run to completion on a large n.
Re: nQueens algorithm - Algorithms Discussion Boards[^]
|
|
|
|
|
Interesting. They mention that the problem has been expanded to a chessboard that's 1000 by 1000.
But they don't mention if there has been a corresponding increase in the number of queens. It would seem that on such a large chessboard, it would be easy to place eight queens so that no two can attack each other.
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
Apply WarCraft rules and open a portal for the team 
Bastard Programmer from Hell 
If you can't read my code, try converting it here[^]
|
|
|
|
|
Richard Andrew x64 wrote: But they don't mention if there has been a corresponding increase in the number of queens
The article itself is incomplete. The synopsis of the actual paper has the real description.
"The n-Queens problem is to place n chess queens on an n by n chessboard"
Richard Andrew x64 wrote: it would be easy to place eight queens so that no two can attack each other.
I wonder if it is a solvable problem to figure out how many possible positions eight queens could be done on a 1000x1000 board. Without using years on a computer.
|
|
|
|
|
jschell wrote: I wonder if it is a solvable problem to figure out how many possible positions eight queens could be done on a 1000x1000 board
42 
|
|
|
|
|
jschell wrote: "The n-Queens problem is to place n chess queens on an n by n chessboard"
Thank you for that clarification!
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
I imagine one could generalize on the knight-pattern that is required of any solution to solve any n-sized board, to find at least one solution. I'll ponder it, but one of the things these people love to do is spout permutations, which look daunting, but there are ways to solve problems other than by "smart" permutations. Finding required patterns is one of them.
|
|
|
|
|
since we are on this subject...
The smallest board with a possible solutions is 4x4 right?
I don't think it is possible to solve a 3x3. 
I'm sure a 2x2 is unsolvable.
Why does google say that it took 1ms to solve a 1x1 board?
Also, their grid makes it look like it took 0ms to solve the 3x3 and 4x4 but I believe they are trying to say they're unsolvable. They really should've been more clear:
The N-queens Problem Optimization: Google Developers[^]
Look at their chart all the way at the bottom.
EDIT
Oh, I stared at the chart longer...
It is actually just that the data is unaligned with the headers at the top of the chart.
They are actually saying there are 0 solutions for board sizes 2 and 3.
I'm using Chrome, you'd think their chart would look right.
|
|
|
|
|
I have added the modifier UPDATED because there are some add-ons that come up in a search, but they all seem to be outdaated.
modified 1-Sep-17 15:49pm.
|
|
|
|
|
OK, I'm gonna be that guy...
Who manual edits cookies, and why?
I once wrote a cookie browser, and even having done this, I have no idea why you'd want to edit them.
|
|
|
|
|
Maybe it's for some QA testing.
|
|
|
|
|
I don't know either, but evidently, there are a lot of apps out there for this.
|
|
|
|
|
OK, the reason is that when I go to the Yahoo Finance page to look at the ticker symbols that I have a position in, they are contained by default in the Recently Viewed section; the problem is that sometimes other ticker symbols get put in there that I don't like - e.g., the cancer stick maker Altria  - and I'd like to be able to remove them. Now, I could get around this by selecting my Watchlist, which has only the symbols that I want, but a lot of times I'm not in mood to dig around. And I figure that I could also make some changes to other cookies to get rid of behavior that I don't like, without blowing up the cookies, which would force me to enter passwords, etc.
|
|
|
|
|
So...once the cookie for the Yahoo Finance site contains certain information, you don't want it to change from that point forward?
Couldn't you change the ACLs to essentially remove all write permissions on the cookie file?
(I have no idea if Firefox uses separate files for individual site cookies...so this might not apply at all)
|
|
|
|
|
What's wrong with the Storage Inspector in the built-in developer tools?
You can edit cookies by double-clicking inside cells in the Table Widget and editing the values they contain.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Storage Inspector is out of date.
|
|
|
|
|
What does that mean? It's part of Firefox, so it's not like it's incompatible with the latest version or anything. 
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Hi All,
Friday afternoon does anything useful get done on a Friday, the JIRA server has fallen over and can't be restarted(?) Before I go home so look busy it is then...
|
|
|
|
|
For mine, server or no, by applying standard rounding the weekend actually starts at lunch time on Friday.
signature upgrading ... please wait.
|
|
|
|
|
Quote: Hoist up the Jira B
I feel so broke up I want to go home
Let me go home
|
|
|
|
|
Quote: So hoist up the John B's sail
See how the main sail sets
Call for the Captain ashore
Let me go home, let me go home
I want to go home, yeah yeah
Well I feel so broke up
I want to go home
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
