This is a different problem. Not what yesterday's description/linked page were saying (better: implying). But, no problem...
If you have a m number of queens already placed in random (but valid) locations, I would also go with my preliminary idea of finding patterns. Rather than starting from the top/bottom, you start from one of the existing queens (because you have to know their location) and check the acceptable positions from it by applying the corresponding pattern (as suggested in the comments in the lower part: knight-like movements); then move the next queen or, when not having more placed queens available, start applying the corresponding pattern for empty locations. It certainly seems doable with negligible time requirements and by involving only a bit more of effort/slightly complex algorithm.
Thanks. But this is neither the Slashdot description nor the page linked from it. That page is referred by a link inside the linked page, which BTW I don't recall seeing yesterday (there was a link to the PDF version of the actual paper which I cannot find anymore). They might have updated that description.
Anyway, my original post was meant to make clear what wasn't clear and your reference is precisely reinforcing that impression, as far as having to go to the page linked by the page linked in the summary isn't precisely clear:)
(and here's the important part) some of the queens have already been placed and cannot be moved.
Where is exactly that point explained in the description or the linked paper? How many queens have already been placed? Where have those queens been placed? Describe the problem properly and I will update my impressions.
"What would be necessary would be either a proof that there is an algorithm that can solve the n-Queens Completion puzzle in polynomial time, or a proof that no such algorithm exists.”
Can you please tell me where you can find that sentence in the summary or in the linked page?
seriously, you're out of your fucking league on this one and really don't know what you're talking about. fwiw, it's out of my league too, but i'm at least smart and educated enough to understand what the problem is asking.
LOL. It is probably out of your league, it is certainly not out mine. Nothing even slightly related to software development, mathematics and even abstract description of whatever reality (the fact of not liking too much abstract whatever without a close relationship to actual applicability doesn't mean that I cannot deal with that; a different story is that abstract-ideas-focused people tend to not be too objective, honest and sensible-critic-friendly, what traditionally was associated with scientific/engineering/technical fields, via random and unmotivated attacks "like this is too much for you". LOL. Abstractly and wrongly repeating a few mantras isn't out of the league anyone; properly understanding the underlying concepts and sensibly criticising them is certainly out of the league of many people, but not mine).
Just because of that statement, you seem a perfect candidate for this cult of knowing nothing talking a lot and feeling attacked/attacking to anyone saying anything even slightly outside what you have trained to repeat. I guess that you specialise in other abstract sub-field which you think that is completely unrelated to this, but actually is pretty much the same: nicely-wrapped ignorance (at least, when misused). Abstract theories/fields might be extremely helpful when used wisely by sensible people. Blindly believing and defending whatever abstract idea regardless of anything else and attacking anyone sensibly discussing about any of its points is fanaticism. People defending that are fanatics. And the corresponding theory/field stops being scientific-like and becomes religious-/faith/cult-like.
and, yes, the downstream "real-world" implications for submitting something worthy of the prize would be incredible.
As a good fanatic, you aren't listening to what I say or trying to understand my point. You are plainly repeating your ultimate truths by assuming what might be my position. You are plainly having a conversation with yourself (via creating a virtual version of me thinking what you consider that I have to think to allow your replies to make sense). I will repeat it for the last time, so please read the following paragraph very carefully:
I HAVEN'T SAID A WORD ABOUT THE NP/P IMPLICATIONS OF THIS PROBLEM AT ANY POINT. I HAVEN'T COMMENTED ANYTHING ABOUT WHAT I THINK ABOUT NP/P, ITS EVENTUAL RESOLUTION, HOW THIS PAPER OR THIS PROBLEM IS RELATED TO THIS OR ANYTHING EVEN CLOSE TO THAT. MY ONLY MENTION TO ALL THIS HAS BEEN TO MERELY HIGHLY THE FACT THAT THE CLAIMED PRIZE WAS ACTUALLY LINKED TO ASSUMED THAT SOLVING THAT PROBLEM WILL IMPLY TO SOLVE NP/P; THIS IS MENTIONED IN THE LINKED PAGE BUT NOT IN THE SUMMARY AND THIS IS ALL WHAT I SAID.
Now you can read each single of my comments in this thread and confirm by yourself that statement: all the references NP/P have been done by people like you with whatever (understanding) problems, unwilling to have a proper conversation to understand others and plainly wanting to fanatically defend their ideas against non-existent attacks. All my posts here were firstly focused on clarifying the confusing bits in both the summary and the linked page; and afterwards, on highlighting that a trivial solution (where the time requirements are negligible) is possible for this problem via forgetting about chess and facing it the location of elements under certain constraints following a very clear pattern which might slightly change with increasing/decreasing sizes. Another user wrote what I consider a sensible implementation and plainly referred to that implementation as a good example of my ideas. Additionally, I have been correcting lots of unmotivated misunderstandings, (slight) attacks and plainly dishonest attitudes of people whose motivations I cannot e
No. It is a convention used mostly by people having CS degrees. It is an as efficient way to communicate things as any other methodology by assuming that all the interlocutors are comfortable by relying on those concepts. I do specialise in improving efficiency and building very efficient algorithms completely from scratch and have never needed these concepts. I have fluidly communicated with other programmers in many different situations without relying on those ideas. They are purely and simply an alternative (out of many different ones) to perform a very simple task. You might be more comfortable by relying on it, I am not.
The concept of reference, loops and memory allocation?
Loops are one of the most basic parts of programming, which you have to use no matter what language or implementations are you working on. Memory allocation isn't a problem in programming languages since quite a few year ago; but, when dealing with older languages (e.g., right now I am developing a very demanding application in pure C), you also need to forcibly account for that. Reference is again an abstract concept with different implementations in different languages on which you might rely, but might not need to understand its abstract/theoretical definition.
One thing is learning basics which might be done in many different ways and by focusing on different aspects; a different story is becoming an experienced/professional programmer what includes not just your theoretical background/initial learning, but many other things (e.g., general/technical knowledge and attitude, predisposition, really linking all the world, systematically learning, etc.) and mainly lots of practice, ideally under demanding enough conditions.
Do not piss on us and tell us it's raining. You have not solved any NP-complete problem
Where have I even remotely suggested such a thing?!
You may not be self-aware enough to detect your own bullshit, but everyone else can smell it.
What bullshit? What are you talking about and with whom? I have created nothing, another user did, but there is an actual code down this thread! A properly working sensible algorithm which might need some tweaking, but already represents a very good first step to solve this specific problem (nobody said anything about solving any generic nothing). Something which anyone with a bit of (programming) knowledge should be able to almost immediately understand; not like the c++ code making no sense at any level which someone (you?) wrote for a reason I don't even know (still waiting for his explanations). Is this what you call bullshiting? Writing a completely nonsensical code and expect your audience to be so ignorant that they cannot even analyse it?! Nobody has implied that this has any effect on your precious NP/P, all this is in your head and in the misinterpretation-prone attitude you are showing right now.
I honestly don't know what is the matter with some people online, labelling themselves as software developers but being scared of code! Not even understanding a simple algorithm! And reacting aggressively with anyone on account of their own lacks! Constantly lying and thinking that everyone lies to them?! It is freaking code!! It is exactly what it is!! There is no possible interpretation. It works/delivers what is expected or not! All your world of bullshit(ing), believing, abstract talking, etc. should ideally have no place in a so technical field as programming! You create problems where there is none! Why don't you try to just have the opposite behaviour? Why don't you enjoy your world of peculiarities, but let other people do things in a different way and stop assuming craziness and provoking nonsensical chaos? No (even slightly) sensible person can read most of the posts I have been writing in this thread (+ the original posts provoking them) and believe that this is normal! You have to make a very relevant effort to misunderstand so simple, to the point and adaptable ideas (+ my readiness to explain anything further) as the ones I wrote here. This is one of the few scenarios where "the problem is just you" is fully applicable. Seriously, go deal with those like you and stop bothering actually honest, knowledgeable people exclusively interested in knowing/understanding/solving.
If you want to spend time on something actually relevant, you should take a look at the PHP code in the lower part of this thread. It might need some tweaking, but it already represents a first good enough approach. The time requirements there are negligible.
OK. I am always ready to recognise my errors and even to give as many chances as necessary to people really meaning well. I guess that the fact that my first impression about your intentions was really bad is pretty clear; even that I have had quite few bad experiences with misunderstanding-prone individuals. But if I made a mistake, I would be more than happy to correct it. And even in case of realising that your intention was good, regardless of the accuracy of your approach, I would also apologise for my reaction. So, please, explain how this algorithm is expected to accomplish what is intended here.
At a first sight, I see the following: - Two references to random variables (just this is more than enough to know that it will not deliver what is expected). - A loop whose definition and iterations are quite unclear and, in any case, doesn't seem to obey to the expected X/Y positions within the board. - That energy method performs unclear-why iterations through the main array (containing not sure what, because 2D information is expected), calculates a mysterious double variable by analysing the relationship between all the positions (curious point: there is no arguments; so that function behaves always identically independently upon the given iteration in the main loop, it only cares about the contents of the main array) and returns a double variable whose exact contribution to the main loop is also a mystery.
All what I can see here is that your algorithm doesn't meet the basic requirements (i.e., analysing/returning a 2D collection by following a set of very strict rules), relies on random analysis (what is completely against all what this is about) and seems extremely unclear regarding what it is expected to accomplished in each single step.
Please, explain how you were expecting to account for the proposed problem in this way or, at least, what was your impression regarding the expected outputs/behaviour. You could even just tell me why you thought that this approach (which perhaps you took from somewhere else and which you used at a different point for other purpose) was helpful here. You can use a very simple example to illustrate your ideas, if you wish; there is a very nice picture in the Wikipedia page about the 8-queen problem showing how a solved setup looks like. You could just tell me how you were expecting your algorithm to deliver anything even close to that. I look forward to understanding better your intention/contribution and to eventually apologising for having misinterpreted your post.
Actually we already know how to solve the problem efficiently for all n greater than 3
No idea who is "we" and what "efficiently" means in this context, but this is the first time I see/think about this problem and my first impression regarding how to face it doesn't seem too improvable. There seems to be clearly-defined, regularly-varying patterns whose understanding/implementation/validation doesn't look too difficult; and the resulting algorithm would solve the problem for n almost immediately (take a look at a PHP code below written by someone else to understand better what I mean).
If, when I started posting in this thread, I was aware about the numerous confusions and misunderstanding that what I thought evident would provoke, I would have started working right away on implementing+validating an algorithm and posting it here, rather than spending so much time by addressing abstract concerns. I have learned my lesson and this is what I will do next time.
I have already spent too much time here replying people showing what I consider different forms of ignorance, poor-understanding and even dishonesty. Although your intention + knowledge/understanding capabilities aren't completely clear after reading your post (which honestly I have just quickly skimmed through), I don't feel like starting what looks like a new set of nonsensical misinterpretations going nowhere. Sorry, but I will plainly ignore what you wrote.
The Queen's problem has nothing to do with standard chess engines
Certainly it doesn't, but after a quick look at the paper and after how they seem to be facing the problem, they don't seem to be aware about that fact. I would personally never have thought about facing this situation in that way; you can read some of my comments in the lower part of this thread to confirm that point.
For something that is a long standing, well documented problem,
Honestly, this is the first time when I have thought about this problem and it seemed pretty straightforward to me. As commented below, the first approach coming to my mind (and the one I have right now, after having discussed with different people here) was to analyse the solved 8x8, look for the sure trends related all the positions of the queens and care about variations on said pattern provoked by increase/decrease of the board size; by assuming this to be relatively easy because of all the variations being very regular and symmetrical. But even in case of being proven a complex pattern, I would have stick to that approach anyway and wouldn't ever consider the option of building a chess-like algorithm (i.e., one accountings for the queen moves and analysing forward/backwards).
there is no excuse for being that wrong and that sure you've solved it
Wrong? Look down this thread, where you can find a reasonably good first step to solve this problem for any n in PHP. I didn't write it, but that person came from an equivalent approach which was my first thought after having read this problem. If I knew that there was some money really involved or anything making my effort worthy, I would certainly create an algorithm solving this problem for any n. And my approach would start from similar lines to that code below.
If you have years of tech experience, then you should be well aware that the quality of one fluff piece news article is not an excuse for misunderstanding something widely written about.
I am still not sure how I have misunderstood anything, but I have seen quite a few people here misunderstanding lots of things which I consider pretty evident. All what I have done was, initially, correcting the numerous lacks in the description of the problem; and afterwards, highlighting issues which I considered evident (e.g., even despite having clear what the intention of the authors is, the proposed example is bad because can be solved much easily than what they seem to think).
Regarding your "widely written about", note that I mainly focus on objectively analysing the given conditions and, as a first resource, I usually rely on my own knowledge/expertise. If I understand that the problem is too complex, I might try to find already-done solutions; rarely by blindly applying them (I do almost nothing blindly) but mostly to speed up my understanding about the problem and the best way to proceed. In this specific case, I didn't see the need of doing such a thing and that's why I didn't do any research about existing solutions to this problem.
Down this thread, you can find a PHP code delivering what is expected. It might not be perfect (not really sure), but it is certainly very close to solve the problem here. And the size of the code (+ effort for an actually knowledgeable person, actually understanding the problem and actually delivering a reasonably acceptable solution) is similar to your crap. See? Doing something useful or relevant requires pretty much the same effort than making a fool of yourself, lying and contributing towards creating a shitty world/environment. So, if you are not in a position to properly understand whatever issue for whatever reason, why don't you make all of us a favour and plainly don't do anything? Why do you think that sharing crap has any value to anyone, that the whole world has to be understanding with whatever problems you have? Knowledgeably, actively, relevantly, positively (what also includes reasonable critics) contribute or just do nothing. It isn't too difficult, right?
I am not sure that you can blindly apply what works for 8x8 to any size without doing anything else, but the eventual modifications are likely to be quite irrelevant. As written above, you should be able to come with a reasonably reliable approach just by analysing the simpler scenarios (7x7 and 9x9) and see how lower/higher sizes affect the original pattern. Also properly validating this approach, even just for a few simpler scenarios isn't completely straightforward (at least, not as straightforward as writing my thoughts here:)). Anyway, your overall approach and this PHP algorithm look certainly nice; mainly after having read how difficult seem for some people to understand what I thought that was pretty evident (= first idea coming to my mind after seeing the problem).
(I am reposting by removing the unnecessary repetitions, a direct consequence of my Sunday-morning reliability:))
I gotta say this is interesting, but maybe not workable.
Even before testing it and by being completely aware that such a proceeding is certainly not recommendable, I am quite sure that it is perfectly (and relatively simply) doable.
Is there a simple algorithm for locating the solved 8x8 into a 10x10 and then placing the remaining 2 queens into the open squares?
This isn't exactly what I meant. My approach was to use the solved sample to understand how to proceed, to find out the trend (by including how it varies with bigger/smaller board sizes) and to implement it. What the parent poster is proposing (i.e., starting in a given position and moving like the knight would do) seems as a descriptive enough way to show what I mean. Finding the pattern doesn't mean to exactly replicate the given conditions regardless of anything else, but to find out how are the pieces located with respect to each other/the board and how these positions change with increasing/decreasing sizes. The increases/decreases of board/number of queens are regular so just focusing on the simpler scenarios (e.g., 7*7 and 9*9) should be more than enough to come up with a reasonably good approach.
But even in case that I was wrong (very unlikely to happen, even though I haven't done any test; but I have lots of experience on this front and I honestly don't see a problem here) and that the eventual algorithm was much more complicated; even in the worst scenario possible, this problem should always be faced by avoiding the tremendous over-complication of accounting for all the possible movements (even after coming up with a way to reduce them). This problem is about finding final positions and you should create an algorithm delivering those; creating an algorithm properly understanding complex + time-consuming behaviours when you could easily do it manually (for simple scenarios + find pattern) is a clearly bad approach. Even worse, these guys seem to be relying on standard chess approaches which are unnecessarily expensive under the current conditions.
And we have to consider that there are many unique solutions for 8x8
No we haven't. This is one of the ways to face this problem wrongly: thinking in it as it would chess, which is a way much more complex reality than what we really have here. All what you need is a single way for it to work; and you need to focus on the most scalable (pattern-find-friendly) version. At first sight, that picture/parent proposal seemed to me as a really good one, but it might not be proven good enough and you might have to analyse a different one. You might even consider different approaches for different sizes.
Ah! Come on! This has been my worse wrong-posting here since ever. Please, read only up to the first "You might even consider different approaches for different sizes.", otherwise you might get yourself into an endless loop. LOL
I gotta say this is interesting, but maybe not workable.
Even before testing it and by being completely aware that such a proceeding is certainly not recommendable, I am quite sure that it is perfectly (and relatively simply) doable.
Is there a simple algorithm for locating the solved 8x8 into a 10x10 and then placing the remaining 2 queens into the open squares?
This isn't exactly what I meant. My approach was to use the solved sample to understand how to proceed, to find out the trend (by including how it varies with bigger/smaller board sizes) and to implement it. What the parent poster is proposing (i.e., starting in a given position and moving like the knight would do) seems as a descriptive enough way to show what I mean. Finding the pattern doesn't mean to exactly replicate the given conditions regardless of anything else, but to find out how are the pieces located with respect to each other/the board and how these positions change with increasing/decreasing sizes. The increases/decreases of board/number of queens are regular so just focusing on the simpler scenarios (e.g., 7*7 and 9*9) should be more than enough to come up with a reasonably good approach. But even in case that I was wrong (very unlikely to happen, even though I haven't done any test; but I have lots of experience on this front and I honestly don't see a problem here) and that the eventual algorithm was much more complicated; even in the worst scenario possible, this problem should always be faced by avoiding the tremendous over-complication of accounting for all the possible movements (even after coming up with a way to reduce them). This problem is about finding final positions and you should create an algorithm delivering those; creating an algorithm properly understanding complex + time-consuming behaviours when you could easily do it manually (for simple scenarios + find pattern) is a clearly bad approach. Even worse, these guys seem to be relying on standard chess approaches which are unnecessarily expensive under the current conditions.
And we have to consider that there are many unique solutions for 8x8
No we haven't. This is one of the ways to face this problem wrongly: thinking in it as it would chess, which is a way much more complex reality than what we really have here. All what you need is a single way for it to work; and you need to focus on the most scalable (pattern-find-friendly) version. At first sight, that picture/parent proposal seemed to me as a really good one, but it might not be proven good enough and you might have to analyse a different one. You might even consider different approaches for different sizes.
I gotta say this is interesting, but maybe not workable.
Even before testing it and by being completely aware that such a proceeding is certainly not recommendable, I am quite sure that it is perfectly (and relatively simply) doable.
Is there a simple algorithm for locating the solved 8x8 into a 10x10 and then placing the remaining 2 queens into the open squares?
This isn't exactly what I meant. My approach was to use the solved sample to understand how to proceed, to find out the trend (by including how it varies with bigger/smaller board sizes) and to implement it. What the parent poster is proposing (i.e., starting in a given position and moving like the knight would do) seems as a descriptive enough way to show what I mean. Finding the pattern doesn't mean to exactly replicate the given conditions regardless of anything else, but to find out how are the pieces located with respect to each other/the board and how these positions change with increasing/decreasing sizes. The increases/decreases of board/number of queens are regular so just focusing on the simpler scenarios (e.g., 7*7 and 9*9) should be more than enough to come up with a reasonably good approach. But even in case that I was wrong (very unlikely to happen, ev
About a half a minute on my laptop after programming for about 20 minutes. I am sure that's not what the prize is about.
There seems to be lots of misunderstanding(-prone people) in this thread (and I have to still read a few replies below; I don't want even to imagine what is waiting for me down there! Pff). Please, re-read my comment and tell me where I have written any indication regarding the proceeding or expectations in this specific problem? I have plainly summarised what the linked page (+ a sensible interpretations of its contents because it is very unclear) says. That professor is expressly saying that for n=1000, the time requirements are already unacceptably high and that's why I interpret that they would consider a good enough solution anything working reasonably fast under these conditions. By bearing in mind that the time requirements are already tremendously high for that value, it makes sense to assume that a reasonably-fast solution under these conditions will already be fast enough for much higher values of n.
Now, your code. Well... it pure (dishonest) nonsense which might not even compile (didn't test it and I am not used to deal with C++, so I cannot tell for sure at first sight). Apparently, you have written a loop performing some variations in an array (presumably including the 1000 queens; although you should have written it to deal with n queens & n*n board; although well... why bothering right?). You are calling a weird method with a weird name (energy) performing weird things and whose point within the loop is unclear (wasting time for no reason? Looking cool because writing nested loops is cool? Not sure). The algorithm is basically built on random numbers, calculations and actions which, even after a very quick look, are clearly not having anything to do with what this problem is about.
Ironically, an efficient solution for this problem isn't too difficult, could be built quite quickly too and the code would be pretty much of the same size than the one you wrote (there is some comments about this in the posts below; and I am afraid that I will have to write even further clarifications right now, so even you should be able to understand what is a pretty simple concept). But, unlikely your sad attempt, It would actually be solving the problem; rather than proving your low understanding skills, what seems a dishonest(ly aggressive) behaviour and not precisely a very solid programming approach.
In summary, your algorithm is pure crap and kind of tells something about your personality and expectations. Are you used to deal with lying people to whom you usually lie, right? You don't solve things and try to understand/be understood, you plainly censor anyone saying anything even slightly different than what you consider acceptable/can understand (apparently, not too much) and intentionally rely on what you think that are obscure ways (although really are petty attempts only showing your ignorance and the one of those with whom you usually deal) to prove your underlying point!? If are used to situations where you can show this piece of crap to someone with even a tiny understanding of programming (in any language) and that person says to you "OK, no problem", you would be certainly surrounded by extremely ignorant and dishonest people. The only sensible behaviour of a person (not even a programmer) facing something which cannot fully understand is trying to understand it (even via asking you), without daring to make the slight decision like appraising/criticising it before that happens. Just the fact that you think that throwing a piece of crap making absolutely no sense in this context and expecting (actually knowledgeable!) people to blindly accept that and plainly lie to you ("it is ok"), tells quite a lot about the quality of the knowledge, principles, expectations of quite few "programmers" or "software developers" (as whatever you choose to self-identify). Please, go back to your made-up world of abstract words, liars and poor-quality everything and don't bother me again with your pathetic nonsense.
I am afraid that the only not getting it is you. Read my previous comment again, mainly the second paragraph. I recommend you to do it slower this time.
I know what his algorithm does. And for n=1000, it will take more time than a billion universes put together.
The second sentence seems to indicate that the first sentence is wrong and you didn't understand my previous comment (read it again, please). Here comes more help just in case: you want to find out the right locations for the queens right? Now visit the Wikipedia article which I am linking in my previous comment and look at the picture on the RHS, this is how the queens have to be located in an 8x8. Tell me, how long it would take you to come to that conclusion? I will answer it for you: a negligible amount of time because you don't need to find all the possible moves of the queens, but plainly replicating the shown structure; or, as suggested by the parent post, start from certain cell and locate one queen, then move like a knight and locate another one and so on.
Do you get the idea now? You don't need to perform lots of calculations, you don't need to account for all the possible combinations of moves, all what you need is to create a pretty simple algorithm locating objects in certain places for an increasingly growing board by following a pretty simple pattern. Clear now? Do you think that our universe will be here during the next few seconds required for any computer to perform all these actions for virtually any size of n?
Of course... I'm curious with regards to the queen's puzzle. This strikes me as a problem that should be solved by graph theory in a means that could later be reduced in complexity. The proof however seems to me from brief evaluation to have a solveable root within a minimal spanning tree or similar.
Nothing even close to these lines. The solution is written in a post below, which I have completed with some additional help to get the idea. Basically, treating the problem not as chess (because this isn't chess), but as queens under restricted conditions which have to be in certain positions (= patterns which aren't too difficult to find after looking at a solved situation).
Clarification for you + the parent: using the methodology (or computer or chair or pencil, etc.) which makes you work more comfortable is certainly fine. Blindly believing in pseudo-magical properties for said methodology starts sounding kind of weird, but it is OK with me (I live and let live). But when you start thinking that you can arbitrarily impose your restricted perception to others and use such an ignorance (because someone blindly believing in whatever without considering anything else is clearly a very ignorant person) to plainly attack anyone acting differently; in that exact moment, you become the kind of fanatic idiot who deserves to be treated as such.
You can claim your prize as soon as your algorithm put onto a standard computer came up with a solution to the "n queens on an n x n board" with n=1000.
No. I can bet you 1 million (I don't having this amount with me, but I might be getting it soon. LOL) right now that the parent poster will not get anything. This was some kind of promotion of their paper by bringing into picture that other prize for proving N/NP problem (their site links to the prize's site). But they seemed to have made their message too commercial and too unclear until the point of seeming to be proposing a different thing.
On the other hand, that algorithm (or another one on these lines) will certainly deliver what is expected for any number of n. I was about to write something like that when I saw the parent post. At least my approach would be to replicate the solved 8-queen setup which, as you can see in the picture, is quite regular; and, as proposed by the parent poster, lets all the queens at knight-movement distances. This is the only kind of approach which will ever come to my mind (but I am a quite experienced programmer with lots of experience in coming up with efficient algorithms, so perhaps other people might not think like me) when trying to solve this problem. You only want to locate certain elements (queens), why to consider others (remaining pieces)? You know that there is a solved subset (8 queens), why not taking it as starting point? Are the movements/dimensions changing regularly? Yes. Solution: look for the surely-existing pattern, implement it and job done.
Done. There is a simple solution, but the prize is about being able to prove there is a simple solution, without coming up with it (P = NP)
Setting some sensible constraints to a problem makes sense; even expecting a specific solution out of different possibilities. But just thinking about a very specific approach while (poorly) enunciating a problem doesn't make other solutions invalid; the person enunciating the problem is the one being wrong.
From the confusing summary and linked page, your approach (didn't test it, but looks fine; I mean something on these lines) is the solution. It is not the solution they expect because they made a mistake by proposing a so bad example. A problem on these lines should always be faced by relying on an approach like yours, an algorithm exclusively focusing on queens (+ finding the patterns allowing the intended reasonably straightforward distribution to happen).
If you don't understand what I just said, welcome to Slashdot, we (used to) talk tech stuff here
I am a senior programmer with 2 university degrees (one of them in engineering) who has been full-time working on software development for over the last 8 years. I know what your time complexity is and its exact applicability to my work: none. I also have been contributing here relatively often during the last years; most of the times by mostly focusing on "tech" issues. What do you think that is more "tech": actually solving a problem by coming up with the optimal algorithm; or getting lost (read below) on abstract ideas originally intended to precisely help you solve that problem more efficiently.
In any case, I was plainly highlighting an evident, reality: unclear and misleading description. But I could even say that this whole proposal doesn't make too much sense as far as solving that problem much quicker is relatively easy; but this isn't the intended goal. The goal is to improve the way in which a wrong approach (= using a standard chess engine performing a standard analysis when this specific situation calls for much less than that) solves a problem by plainly ignoring the obvious solution of coming up with the more efficient, to the point approach. So, in the best scenario, this whole proposal is a (confusing) bad example to explain certain theoretical idea whose "tech" character might not be too clear.
Not only that, but if an 8-queen solution works on an 8x8 board, it'll work just as well on a 1000x1000 or a 10k x 10k board,
The summary and even the linked page are a bit confusing on this front, but the paper is clearer. Apparently, this isn't an 8-queen problem, but an n-queen problem in an n*n board. The exact conditions aren't too clear either (e.g., "solve the problem really fast"), but it seems that creating an acceptably quick solution for n = 1000 should be enough.
Slashdot Mirror
This is a different problem. Not what yesterday's description/linked page were saying (better: implying). But, no problem...
If you have a m number of queens already placed in random (but valid) locations, I would also go with my preliminary idea of finding patterns. Rather than starting from the top/bottom, you start from one of the existing queens (because you have to know their location) and check the acceptable positions from it by applying the corresponding pattern (as suggested in the comments in the lower part: knight-like movements); then move the next queen or, when not having more placed queens available, start applying the corresponding pattern for empty locations. It certainly seems doable with negligible time requirements and by involving only a bit more of effort/slightly complex algorithm.
Thanks. But this is neither the Slashdot description nor the page linked from it. That page is referred by a link inside the linked page, which BTW I don't recall seeing yesterday (there was a link to the PDF version of the actual paper which I cannot find anymore). They might have updated that description.
:)
Anyway, my original post was meant to make clear what wasn't clear and your reference is precisely reinforcing that impression, as far as having to go to the page linked by the page linked in the summary isn't precisely clear
You're not even solving the right problem.
?! OK.
(and here's the important part) some of the queens have already been placed and cannot be moved.
Where is exactly that point explained in the description or the linked paper? How many queens have already been placed? Where have those queens been placed? Describe the problem properly and I will update my impressions.
"What would be necessary would be either a proof that there is an algorithm that can solve the n-Queens Completion puzzle in polynomial time, or a proof that no such algorithm exists.”
Can you please tell me where you can find that sentence in the summary or in the linked page?
seriously, you're out of your fucking league on this one and really don't know what you're talking about. fwiw, it's out of my league too, but i'm at least smart and educated enough to understand what the problem is asking.
LOL. It is probably out of your league, it is certainly not out mine. Nothing even slightly related to software development, mathematics and even abstract description of whatever reality (the fact of not liking too much abstract whatever without a close relationship to actual applicability doesn't mean that I cannot deal with that; a different story is that abstract-ideas-focused people tend to not be too objective, honest and sensible-critic-friendly, what traditionally was associated with scientific/engineering/technical fields, via random and unmotivated attacks "like this is too much for you". LOL. Abstractly and wrongly repeating a few mantras isn't out of the league anyone; properly understanding the underlying concepts and sensibly criticising them is certainly out of the league of many people, but not mine).
Just because of that statement, you seem a perfect candidate for this cult of knowing nothing talking a lot and feeling attacked/attacking to anyone saying anything even slightly outside what you have trained to repeat. I guess that you specialise in other abstract sub-field which you think that is completely unrelated to this, but actually is pretty much the same: nicely-wrapped ignorance (at least, when misused). Abstract theories/fields might be extremely helpful when used wisely by sensible people. Blindly believing and defending whatever abstract idea regardless of anything else and attacking anyone sensibly discussing about any of its points is fanaticism. People defending that are fanatics. And the corresponding theory/field stops being scientific-like and becomes religious-/faith/cult-like.
and, yes, the downstream "real-world" implications for submitting something worthy of the prize would be incredible.
As a good fanatic, you aren't listening to what I say or trying to understand my point. You are plainly repeating your ultimate truths by assuming what might be my position. You are plainly having a conversation with yourself (via creating a virtual version of me thinking what you consider that I have to think to allow your replies to make sense). I will repeat it for the last time, so please read the following paragraph very carefully:
I HAVEN'T SAID A WORD ABOUT THE NP/P IMPLICATIONS OF THIS PROBLEM AT ANY POINT. I HAVEN'T COMMENTED ANYTHING ABOUT WHAT I THINK ABOUT NP/P, ITS EVENTUAL RESOLUTION, HOW THIS PAPER OR THIS PROBLEM IS RELATED TO THIS OR ANYTHING EVEN CLOSE TO THAT. MY ONLY MENTION TO ALL THIS HAS BEEN TO MERELY HIGHLY THE FACT THAT THE CLAIMED PRIZE WAS ACTUALLY LINKED TO ASSUMED THAT SOLVING THAT PROBLEM WILL IMPLY TO SOLVE NP/P; THIS IS MENTIONED IN THE LINKED PAGE BUT NOT IN THE SUMMARY AND THIS IS ALL WHAT I SAID.
Now you can read each single of my comments in this thread and confirm by yourself that statement: all the references NP/P have been done by people like you with whatever (understanding) problems, unwilling to have a proper conversation to understand others and plainly wanting to fanatically defend their ideas against non-existent attacks. All my posts here were firstly focused on clarifying the confusing bits in both the summary and the linked page; and afterwards, on highlighting that a trivial solution (where the time requirements are negligible) is possible for this problem via forgetting about chess and facing it the location of elements under certain constraints following a very clear pattern which might slightly change with increasing/decreasing sizes. Another user wrote what I consider a sensible implementation and plainly referred to that implementation as a good example of my ideas. Additionally, I have been correcting lots of unmotivated misunderstandings, (slight) attacks and plainly dishonest attitudes of people whose motivations I cannot e
(I wrongly thought that this was a reply to one of my comments. Oopsie! To many messages not precisely too appealing for a Sunday. LOL)
Isn't complexity among the most basic knowledge
No. It is a convention used mostly by people having CS degrees. It is an as efficient way to communicate things as any other methodology by assuming that all the interlocutors are comfortable by relying on those concepts. I do specialise in improving efficiency and building very efficient algorithms completely from scratch and have never needed these concepts. I have fluidly communicated with other programmers in many different situations without relying on those ideas. They are purely and simply an alternative (out of many different ones) to perform a very simple task. You might be more comfortable by relying on it, I am not.
The concept of reference, loops and memory allocation?
Loops are one of the most basic parts of programming, which you have to use no matter what language or implementations are you working on. Memory allocation isn't a problem in programming languages since quite a few year ago; but, when dealing with older languages (e.g., right now I am developing a very demanding application in pure C), you also need to forcibly account for that. Reference is again an abstract concept with different implementations in different languages on which you might rely, but might not need to understand its abstract/theoretical definition.
One thing is learning basics which might be done in many different ways and by focusing on different aspects; a different story is becoming an experienced/professional programmer what includes not just your theoretical background/initial learning, but many other things (e.g., general/technical knowledge and attitude, predisposition, really linking all the world, systematically learning, etc.) and mainly lots of practice, ideally under demanding enough conditions.
Do not piss on us and tell us it's raining. You have not solved any NP-complete problem
Where have I even remotely suggested such a thing?!
You may not be self-aware enough to detect your own bullshit, but everyone else can smell it.
What bullshit? What are you talking about and with whom? I have created nothing, another user did, but there is an actual code down this thread! A properly working sensible algorithm which might need some tweaking, but already represents a very good first step to solve this specific problem (nobody said anything about solving any generic nothing). Something which anyone with a bit of (programming) knowledge should be able to almost immediately understand; not like the c++ code making no sense at any level which someone (you?) wrote for a reason I don't even know (still waiting for his explanations). Is this what you call bullshiting? Writing a completely nonsensical code and expect your audience to be so ignorant that they cannot even analyse it?! Nobody has implied that this has any effect on your precious NP/P, all this is in your head and in the misinterpretation-prone attitude you are showing right now.
I honestly don't know what is the matter with some people online, labelling themselves as software developers but being scared of code! Not even understanding a simple algorithm! And reacting aggressively with anyone on account of their own lacks! Constantly lying and thinking that everyone lies to them?! It is freaking code!! It is exactly what it is!! There is no possible interpretation. It works/delivers what is expected or not! All your world of bullshit(ing), believing, abstract talking, etc. should ideally have no place in a so technical field as programming! You create problems where there is none! Why don't you try to just have the opposite behaviour? Why don't you enjoy your world of peculiarities, but let other people do things in a different way and stop assuming craziness and provoking nonsensical chaos? No (even slightly) sensible person can read most of the posts I have been writing in this thread (+ the original posts provoking them) and believe that this is normal! You have to make a very relevant effort to misunderstand so simple, to the point and adaptable ideas (+ my readiness to explain anything further) as the ones I wrote here. This is one of the few scenarios where "the problem is just you" is fully applicable. Seriously, go deal with those like you and stop bothering actually honest, knowledgeable people exclusively interested in knowing/understanding/solving.
If you want to spend time on something actually relevant, you should take a look at the PHP code in the lower part of this thread. It might need some tweaking, but it already represents a first good enough approach. The time requirements there are negligible.
Now, take your pill and breathe.
OK. I am always ready to recognise my errors and even to give as many chances as necessary to people really meaning well. I guess that the fact that my first impression about your intentions was really bad is pretty clear; even that I have had quite few bad experiences with misunderstanding-prone individuals. But if I made a mistake, I would be more than happy to correct it. And even in case of realising that your intention was good, regardless of the accuracy of your approach, I would also apologise for my reaction. So, please, explain how this algorithm is expected to accomplish what is intended here.
At a first sight, I see the following:
- Two references to random variables (just this is more than enough to know that it will not deliver what is expected).
- A loop whose definition and iterations are quite unclear and, in any case, doesn't seem to obey to the expected X/Y positions within the board.
- That energy method performs unclear-why iterations through the main array (containing not sure what, because 2D information is expected), calculates a mysterious double variable by analysing the relationship between all the positions (curious point: there is no arguments; so that function behaves always identically independently upon the given iteration in the main loop, it only cares about the contents of the main array) and returns a double variable whose exact contribution to the main loop is also a mystery.
All what I can see here is that your algorithm doesn't meet the basic requirements (i.e., analysing/returning a 2D collection by following a set of very strict rules), relies on random analysis (what is completely against all what this is about) and seems extremely unclear regarding what it is expected to accomplished in each single step.
Please, explain how you were expecting to account for the proposed problem in this way or, at least, what was your impression regarding the expected outputs/behaviour. You could even just tell me why you thought that this approach (which perhaps you took from somewhere else and which you used at a different point for other purpose) was helpful here. You can use a very simple example to illustrate your ideas, if you wish; there is a very nice picture in the Wikipedia page about the 8-queen problem showing how a solved setup looks like. You could just tell me how you were expecting your algorithm to deliver anything even close to that. I look forward to understanding better your intention/contribution and to eventually apologising for having misinterpreted your post.
Actually we already know how to solve the problem efficiently for all n greater than 3
No idea who is "we" and what "efficiently" means in this context, but this is the first time I see/think about this problem and my first impression regarding how to face it doesn't seem too improvable. There seems to be clearly-defined, regularly-varying patterns whose understanding/implementation/validation doesn't look too difficult; and the resulting algorithm would solve the problem for n almost immediately (take a look at a PHP code below written by someone else to understand better what I mean).
If, when I started posting in this thread, I was aware about the numerous confusions and misunderstanding that what I thought evident would provoke, I would have started working right away on implementing+validating an algorithm and posting it here, rather than spending so much time by addressing abstract concerns. I have learned my lesson and this is what I will do next time.
I have already spent too much time here replying people showing what I consider different forms of ignorance, poor-understanding and even dishonesty. Although your intention + knowledge/understanding capabilities aren't completely clear after reading your post (which honestly I have just quickly skimmed through), I don't feel like starting what looks like a new set of nonsensical misinterpretations going nowhere. Sorry, but I will plainly ignore what you wrote.
The Queen's problem has nothing to do with standard chess engines
Certainly it doesn't, but after a quick look at the paper and after how they seem to be facing the problem, they don't seem to be aware about that fact. I would personally never have thought about facing this situation in that way; you can read some of my comments in the lower part of this thread to confirm that point.
For something that is a long standing, well documented problem,
Honestly, this is the first time when I have thought about this problem and it seemed pretty straightforward to me. As commented below, the first approach coming to my mind (and the one I have right now, after having discussed with different people here) was to analyse the solved 8x8, look for the sure trends related all the positions of the queens and care about variations on said pattern provoked by increase/decrease of the board size; by assuming this to be relatively easy because of all the variations being very regular and symmetrical. But even in case of being proven a complex pattern, I would have stick to that approach anyway and wouldn't ever consider the option of building a chess-like algorithm (i.e., one accountings for the queen moves and analysing forward/backwards).
there is no excuse for being that wrong and that sure you've solved it
Wrong? Look down this thread, where you can find a reasonably good first step to solve this problem for any n in PHP. I didn't write it, but that person came from an equivalent approach which was my first thought after having read this problem. If I knew that there was some money really involved or anything making my effort worthy, I would certainly create an algorithm solving this problem for any n. And my approach would start from similar lines to that code below.
If you have years of tech experience, then you should be well aware that the quality of one fluff piece news article is not an excuse for misunderstanding something widely written about.
I am still not sure how I have misunderstood anything, but I have seen quite a few people here misunderstanding lots of things which I consider pretty evident. All what I have done was, initially, correcting the numerous lacks in the description of the problem; and afterwards, highlighting issues which I considered evident (e.g., even despite having clear what the intention of the authors is, the proposed example is bad because can be solved much easily than what they seem to think).
Regarding your "widely written about", note that I mainly focus on objectively analysing the given conditions and, as a first resource, I usually rely on my own knowledge/expertise. If I understand that the problem is too complex, I might try to find already-done solutions; rarely by blindly applying them (I do almost nothing blindly) but mostly to speed up my understanding about the problem and the best way to proceed. In this specific case, I didn't see the need of doing such a thing and that's why I didn't do any research about existing solutions to this problem.
Down this thread, you can find a PHP code delivering what is expected. It might not be perfect (not really sure), but it is certainly very close to solve the problem here. And the size of the code (+ effort for an actually knowledgeable person, actually understanding the problem and actually delivering a reasonably acceptable solution) is similar to your crap. See? Doing something useful or relevant requires pretty much the same effort than making a fool of yourself, lying and contributing towards creating a shitty world/environment. So, if you are not in a position to properly understand whatever issue for whatever reason, why don't you make all of us a favour and plainly don't do anything? Why do you think that sharing crap has any value to anyone, that the whole world has to be understanding with whatever problems you have? Knowledgeably, actively, relevantly, positively (what also includes reasonable critics) contribute or just do nothing. It isn't too difficult, right?
I am not sure that you can blindly apply what works for 8x8 to any size without doing anything else, but the eventual modifications are likely to be quite irrelevant. As written above, you should be able to come with a reasonably reliable approach just by analysing the simpler scenarios (7x7 and 9x9) and see how lower/higher sizes affect the original pattern. Also properly validating this approach, even just for a few simpler scenarios isn't completely straightforward (at least, not as straightforward as writing my thoughts here :)). Anyway, your overall approach and this PHP algorithm look certainly nice; mainly after having read how difficult seem for some people to understand what I thought that was pretty evident (= first idea coming to my mind after seeing the problem).
I gotta say this is interesting, but maybe not workable.
Even before testing it and by being completely aware that such a proceeding is certainly not recommendable, I am quite sure that it is perfectly (and relatively simply) doable.
Is there a simple algorithm for locating the solved 8x8 into a 10x10 and then placing the remaining 2 queens into the open squares?
This isn't exactly what I meant. My approach was to use the solved sample to understand how to proceed, to find out the trend (by including how it varies with bigger/smaller board sizes) and to implement it. What the parent poster is proposing (i.e., starting in a given position and moving like the knight would do) seems as a descriptive enough way to show what I mean. Finding the pattern doesn't mean to exactly replicate the given conditions regardless of anything else, but to find out how are the pieces located with respect to each other/the board and how these positions change with increasing/decreasing sizes. The increases/decreases of board/number of queens are regular so just focusing on the simpler scenarios (e.g., 7*7 and 9*9) should be more than enough to come up with a reasonably good approach.
But even in case that I was wrong (very unlikely to happen, even though I haven't done any test; but I have lots of experience on this front and I honestly don't see a problem here) and that the eventual algorithm was much more complicated; even in the worst scenario possible, this problem should always be faced by avoiding the tremendous over-complication of accounting for all the possible movements (even after coming up with a way to reduce them). This problem is about finding final positions and you should create an algorithm delivering those; creating an algorithm properly understanding complex + time-consuming behaviours when you could easily do it manually (for simple scenarios + find pattern) is a clearly bad approach. Even worse, these guys seem to be relying on standard chess approaches which are unnecessarily expensive under the current conditions.
And we have to consider that there are many unique solutions for 8x8
No we haven't. This is one of the ways to face this problem wrongly: thinking in it as it would chess, which is a way much more complex reality than what we really have here. All what you need is a single way for it to work; and you need to focus on the most scalable (pattern-find-friendly) version. At first sight, that picture/parent proposal seemed to me as a really good one, but it might not be proven good enough and you might have to analyse a different one. You might even consider different approaches for different sizes.
Ah! Come on! This has been my worse wrong-posting here since ever. Please, read only up to the first "You might even consider different approaches for different sizes.", otherwise you might get yourself into an endless loop. LOL
I gotta say this is interesting, but maybe not workable.
Even before testing it and by being completely aware that such a proceeding is certainly not recommendable, I am quite sure that it is perfectly (and relatively simply) doable.
Is there a simple algorithm for locating the solved 8x8 into a 10x10 and then placing the remaining 2 queens into the open squares?
This isn't exactly what I meant. My approach was to use the solved sample to understand how to proceed, to find out the trend (by including how it varies with bigger/smaller board sizes) and to implement it. What the parent poster is proposing (i.e., starting in a given position and moving like the knight would do) seems as a descriptive enough way to show what I mean. Finding the pattern doesn't mean to exactly replicate the given conditions regardless of anything else, but to find out how are the pieces located with respect to each other/the board and how these positions change with increasing/decreasing sizes. The increases/decreases of board/number of queens are regular so just focusing on the simpler scenarios (e.g., 7*7 and 9*9) should be more than enough to come up with a reasonably good approach. But even in case that I was wrong (very unlikely to happen, even though I haven't done any test; but I have lots of experience on this front and I honestly don't see a problem here) and that the eventual algorithm was much more complicated; even in the worst scenario possible, this problem should always be faced by avoiding the tremendous over-complication of accounting for all the possible movements (even after coming up with a way to reduce them). This problem is about finding final positions and you should create an algorithm delivering those; creating an algorithm properly understanding complex + time-consuming behaviours when you could easily do it manually (for simple scenarios + find pattern) is a clearly bad approach. Even worse, these guys seem to be relying on standard chess approaches which are unnecessarily expensive under the current conditions.
And we have to consider that there are many unique solutions for 8x8
No we haven't. This is one of the ways to face this problem wrongly: thinking in it as it would chess, which is a way much more complex reality than what we really have here. All what you need is a single way for it to work; and you need to focus on the most scalable (pattern-find-friendly) version. At first sight, that picture/parent proposal seemed to me as a really good one, but it might not be proven good enough and you might have to analyse a different one. You might even consider different approaches for different sizes.
I gotta say this is interesting, but maybe not workable.
Even before testing it and by being completely aware that such a proceeding is certainly not recommendable, I am quite sure that it is perfectly (and relatively simply) doable.
Is there a simple algorithm for locating the solved 8x8 into a 10x10 and then placing the remaining 2 queens into the open squares?
This isn't exactly what I meant. My approach was to use the solved sample to understand how to proceed, to find out the trend (by including how it varies with bigger/smaller board sizes) and to implement it. What the parent poster is proposing (i.e., starting in a given position and moving like the knight would do) seems as a descriptive enough way to show what I mean. Finding the pattern doesn't mean to exactly replicate the given conditions regardless of anything else, but to find out how are the pieces located with respect to each other/the board and how these positions change with increasing/decreasing sizes. The increases/decreases of board/number of queens are regular so just focusing on the simpler scenarios (e.g., 7*7 and 9*9) should be more than enough to come up with a reasonably good approach. But even in case that I was wrong (very unlikely to happen, ev
About a half a minute on my laptop after programming for about 20 minutes. I am sure that's not what the prize is about.
There seems to be lots of misunderstanding(-prone people) in this thread (and I have to still read a few replies below; I don't want even to imagine what is waiting for me down there! Pff). Please, re-read my comment and tell me where I have written any indication regarding the proceeding or expectations in this specific problem? I have plainly summarised what the linked page (+ a sensible interpretations of its contents because it is very unclear) says. That professor is expressly saying that for n=1000, the time requirements are already unacceptably high and that's why I interpret that they would consider a good enough solution anything working reasonably fast under these conditions. By bearing in mind that the time requirements are already tremendously high for that value, it makes sense to assume that a reasonably-fast solution under these conditions will already be fast enough for much higher values of n.
Now, your code. Well... it pure (dishonest) nonsense which might not even compile (didn't test it and I am not used to deal with C++, so I cannot tell for sure at first sight). Apparently, you have written a loop performing some variations in an array (presumably including the 1000 queens; although you should have written it to deal with n queens & n*n board; although well... why bothering right?). You are calling a weird method with a weird name (energy) performing weird things and whose point within the loop is unclear (wasting time for no reason? Looking cool because writing nested loops is cool? Not sure). The algorithm is basically built on random numbers, calculations and actions which, even after a very quick look, are clearly not having anything to do with what this problem is about.
Ironically, an efficient solution for this problem isn't too difficult, could be built quite quickly too and the code would be pretty much of the same size than the one you wrote (there is some comments about this in the posts below; and I am afraid that I will have to write even further clarifications right now, so even you should be able to understand what is a pretty simple concept). But, unlikely your sad attempt, It would actually be solving the problem; rather than proving your low understanding skills, what seems a dishonest(ly aggressive) behaviour and not precisely a very solid programming approach.
In summary, your algorithm is pure crap and kind of tells something about your personality and expectations. Are you used to deal with lying people to whom you usually lie, right? You don't solve things and try to understand/be understood, you plainly censor anyone saying anything even slightly different than what you consider acceptable/can understand (apparently, not too much) and intentionally rely on what you think that are obscure ways (although really are petty attempts only showing your ignorance and the one of those with whom you usually deal) to prove your underlying point!? If are used to situations where you can show this piece of crap to someone with even a tiny understanding of programming (in any language) and that person says to you "OK, no problem", you would be certainly surrounded by extremely ignorant and dishonest people. The only sensible behaviour of a person (not even a programmer) facing something which cannot fully understand is trying to understand it (even via asking you), without daring to make the slight decision like appraising/criticising it before that happens. Just the fact that you think that throwing a piece of crap making absolutely no sense in this context and expecting (actually knowledgeable!) people to blindly accept that and plainly lie to you ("it is ok"), tells quite a lot about the quality of the knowledge, principles, expectations of quite few "programmers" or "software developers" (as whatever you choose to self-identify). Please, go back to your made-up world of abstract words, liars and poor-quality everything and don't bother me again with your pathetic nonsense.
I don't think you got the joke.
I am afraid that the only not getting it is you. Read my previous comment again, mainly the second paragraph. I recommend you to do it slower this time.
I know what his algorithm does. And for n=1000, it will take more time than a billion universes put together.
The second sentence seems to indicate that the first sentence is wrong and you didn't understand my previous comment (read it again, please). Here comes more help just in case: you want to find out the right locations for the queens right? Now visit the Wikipedia article which I am linking in my previous comment and look at the picture on the RHS, this is how the queens have to be located in an 8x8. Tell me, how long it would take you to come to that conclusion? I will answer it for you: a negligible amount of time because you don't need to find all the possible moves of the queens, but plainly replicating the shown structure; or, as suggested by the parent post, start from certain cell and locate one queen, then move like a knight and locate another one and so on.
Do you get the idea now? You don't need to perform lots of calculations, you don't need to account for all the possible combinations of moves, all what you need is to create a pretty simple algorithm locating objects in certain places for an increasingly growing board by following a pretty simple pattern. Clear now? Do you think that our universe will be here during the next few seconds required for any computer to perform all these actions for virtually any size of n?
Of course... I'm curious with regards to the queen's puzzle. This strikes me as a problem that should be solved by graph theory in a means that could later be reduced in complexity. The proof however seems to me from brief evaluation to have a solveable root within a minimal spanning tree or similar.
Nothing even close to these lines. The solution is written in a post below, which I have completed with some additional help to get the idea. Basically, treating the problem not as chess (because this isn't chess), but as queens under restricted conditions which have to be in certain positions (= patterns which aren't too difficult to find after looking at a solved situation).
Clarification for you + the parent: using the methodology (or computer or chair or pencil, etc.) which makes you work more comfortable is certainly fine. Blindly believing in pseudo-magical properties for said methodology starts sounding kind of weird, but it is OK with me (I live and let live). But when you start thinking that you can arbitrarily impose your restricted perception to others and use such an ignorance (because someone blindly believing in whatever without considering anything else is clearly a very ignorant person) to plainly attack anyone acting differently; in that exact moment, you become the kind of fanatic idiot who deserves to be treated as such.
You can claim your prize as soon as your algorithm put onto a standard computer came up with a solution to the "n queens on an n x n board" with n=1000.
No. I can bet you 1 million (I don't having this amount with me, but I might be getting it soon. LOL) right now that the parent poster will not get anything. This was some kind of promotion of their paper by bringing into picture that other prize for proving N/NP problem (their site links to the prize's site). But they seemed to have made their message too commercial and too unclear until the point of seeming to be proposing a different thing.
On the other hand, that algorithm (or another one on these lines) will certainly deliver what is expected for any number of n. I was about to write something like that when I saw the parent post. At least my approach would be to replicate the solved 8-queen setup which, as you can see in the picture, is quite regular; and, as proposed by the parent poster, lets all the queens at knight-movement distances. This is the only kind of approach which will ever come to my mind (but I am a quite experienced programmer with lots of experience in coming up with efficient algorithms, so perhaps other people might not think like me) when trying to solve this problem. You only want to locate certain elements (queens), why to consider others (remaining pieces)? You know that there is a solved subset (8 queens), why not taking it as starting point? Are the movements/dimensions changing regularly? Yes. Solution: look for the surely-existing pattern, implement it and job done.
Done. There is a simple solution, but the prize is about being able to prove there is a simple solution, without coming up with it (P = NP)
Setting some sensible constraints to a problem makes sense; even expecting a specific solution out of different possibilities. But just thinking about a very specific approach while (poorly) enunciating a problem doesn't make other solutions invalid; the person enunciating the problem is the one being wrong.
From the confusing summary and linked page, your approach (didn't test it, but looks fine; I mean something on these lines) is the solution. It is not the solution they expect because they made a mistake by proposing a so bad example. A problem on these lines should always be faced by relying on an approach like yours, an algorithm exclusively focusing on queens (+ finding the patterns allowing the intended reasonably straightforward distribution to happen).
If you don't understand what I just said, welcome to Slashdot, we (used to) talk tech stuff here
I am a senior programmer with 2 university degrees (one of them in engineering) who has been full-time working on software development for over the last 8 years. I know what your time complexity is and its exact applicability to my work: none. I also have been contributing here relatively often during the last years; most of the times by mostly focusing on "tech" issues. What do you think that is more "tech": actually solving a problem by coming up with the optimal algorithm; or getting lost (read below) on abstract ideas originally intended to precisely help you solve that problem more efficiently.
In any case, I was plainly highlighting an evident, reality: unclear and misleading description. But I could even say that this whole proposal doesn't make too much sense as far as solving that problem much quicker is relatively easy; but this isn't the intended goal. The goal is to improve the way in which a wrong approach (= using a standard chess engine performing a standard analysis when this specific situation calls for much less than that) solves a problem by plainly ignoring the obvious solution of coming up with the more efficient, to the point approach. So, in the best scenario, this whole proposal is a (confusing) bad example to explain certain theoretical idea whose "tech" character might not be too clear.
Not only that, but if an 8-queen solution works on an 8x8 board, it'll work just as well on a 1000x1000 or a 10k x 10k board,
The summary and even the linked page are a bit confusing on this front, but the paper is clearer. Apparently, this isn't an 8-queen problem, but an n-queen problem in an n*n board. The exact conditions aren't too clear either (e.g., "solve the problem really fast"), but it seems that creating an acceptably quick solution for n = 1000 should be enough.