## Solve a 'Simple' Chess Puzzle, Win $1 Million (st-andrews.ac.uk) 125

An anonymous reader brings an important announcement:

*Researchers at the University of St Andrews have thrown down the gauntlet to computer programmers to find a solution to a "simple" chess puzzle which could, in fact, take thousands of years to solve, and net a $1 million prize. Computer Scientist Professor Ian Gent and his colleagues, at the University of St Andrews, believe any program capable of solving the famous "Queens Puzzle" efficiently would be so powerful, it would be capable of solving tasks currently considered impossible, such as decrypting the toughest security on the internet. In a paper*

Devised in 1850, the Queens Puzzle originally challenged a player to place eight queens on a standard chessboard so that no two queens could attack each other. This means putting one queen in each row, so that no two queens are in the same column, and no two queens in the same diagonal. Although the problem has been solved by human beings, once the chess board increases to a large size no computer program can solve it.*[PDF]*published in the Journal of Artificial Intelligence Research today, the team conclude the rewards to be reaped by such a program would be immense, not least in financial terms with firms rushing to use it to offer technological solutions, and also a $1 million prize offered by the Clay Mathematics Institute in America.Devised in 1850, the Queens Puzzle originally challenged a player to place eight queens on a standard chessboard so that no two queens could attack each other. This means putting one queen in each row, so that no two queens are in the same column, and no two queens in the same diagonal. Although the problem has been solved by human beings, once the chess board increases to a large size no computer program can solve it.

## Large size? (Score:3)

How large is that? Many algorithms for simpler problems would fail if the size is multiplied by a big number.

## Re: (Score:3)

"once the chess board increases to a large size no computer program can solve it"

How large is that? Many algorithms for simpler problems would fail if the size is multiplied by a big number.

More to the point, anything larger that 8x8 isn't a chess board - problem solved, where's my money?

## 8 queens? (Score:3)

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, etc. board. Move it over, put it in the same relative location in the 8x8 group at the corner of the larger board, done. So solve for 8x8 and move.

So you'll need to split that money with me, pal. :)

Of course, it's just

slightlypossible that TFS is not an accurate summary of the actual article / problem,## Re: (Score:3)

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.

## Re: (Score:2)

Since this is all really backed by the discussion about NP != P, what you need to do is create a polynomial time solution for it and then that will be "fast enough". If your algorithm executes in exponential time it won't be fast enough.

If you don't understand what I just said, welcome to Slashdot, we (used to) talk tech stuff here. Read this: en.wikipedia.org/wiki/Time_complexity [wikipedia.org].

## Re: (Score:3)

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

## Re: (Score:2)

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

## Re: (Score:2)

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;

## Re: (Score:2)

"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?!"methinks he doth protest too much.

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 educ

## Re: (Score:2)

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/engin

## Re: (Score:2)

holy shit dude you are fucked up.

i was just kidding before. your solution in PHP is genius & you're one of the few on the right track.

## Re: (Score:2)

holy shit dude you are fucked up.

I am not the kind of person who easily jumps to conclusions after a small conversation + minor additional information (e.g., your signature), but I am pretty sure already that your opinion has a very little value for me (and for anyone whose opinion I might consider). You seem the kind of person who can say one thing or right the contrary, by showing exactly the same knowledge and conviction.

i was just kidding before.

Again without being too much into drawing conclusions after a small conversation, I stick to my aforementioned saying

## Re: (Score:2)

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 comfortab

## Re: (Score:2)

But when I am asked about "why did you choose a regex here instead of simply comparing strings" and I explain algorithmic complexity of compilation of a refer into either a DFA or NFA as well the computational complexity of the execution of the compiler result vs the computational complexity of searching string, they look at me like "I thought I was getting good at programming but if you're what a real programmer is, I have a really long way to go."The reason for choosing to use a regex over

## Re: (Score:2)

You can try a recursive solution. For each queen, place that queen somewhere on the board, mark off those squares that are blocked, for the next queen, repeat the same process. Repeat until you have filled the entire grid. You can exploit symmetry. For the first queen, you only need to try 1/8th of the board due to symmetry due to reflection/rotations.

Perhaps there is some number sequence that only applies to boards of given sizes.

## Re: (Score:2)

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 alterna

## Re: (Score:2)

## Re: (Score:2)

## Re: (Score:2)

(C++14 using gcc on Linux)

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <cmath>

int s[1000];

double energy() {

int result = 0;

for (int i = 1; i < 1000; ++i) {

for (int j = 0; j < i; ++j) {

if (std::abs(s[i]-s[j]) == i - j)

## Re: (Score:2)

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, t

## Re: (Score:2)

The program I wrote works. It's a straightforward implementation of simulated annealing (look it up) for this problem, where the word "energy" is the standard term for the thing you are trying to minimize. I didn't bother making it for general n (although you can

## Re: (Score:2)

I confess I didn't understand the code, but that doesn't prevent me asking:

How long did it take to run for n=1,000?

How long will it take to run for n=1,000,000?

## Re: (Score:2)

## Re: (Score:1)

I confess I didn't understand the code

It's fairly straight forward. The "s" array holds numbers from 0 to N, and represents the positions of queens on the board, for example if s[3]==5 then there's a queen at position (3,5). This method of representing the board automatically ensures no two queens share a row or column, so you just have to worry about diagonals.

The "energy" function compares every queen with every other queen to see if they are on the same diagonal, and returns the number that are.

The code starts with numbers all in order in th

## Re: (Score:2)

Thanks. That was very informative.

I don't think 1,000,000 is feasible with this algorithm.

You might be right. It might not be productive either.

## Re: (Score:2)

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

## Re: (Score:2)

## Re: (Score:1)

They are clear: "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.”

## Re: (Score:2)

"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?

## Re: (Score:2)

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, w

## Re: (Score:1)

## Re: (Score:2)

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.

## Re: (Score:1)

## Re: (Score:2)

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

## Re: (Score:2)

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

## Re: (Score:1)

## Re: (Score:2)

It was obvious that the problem wasn't the straightforward placing of queens

As explained, the new conditions (already placed queens) are too relevant as far as they don't affect the main underlying issues here: constant clearly-defined behaviours (movements of the queens; or better: distances between queens to allow a valid position) under regularly varying conditions (+1 queen/column/row). Just by analysing the problem in that way, it is clear that there is a more or less consistent pattern regardless of its complexity. The pure combinatorics/trial-and-error approach tends to be e

## Re: (Score:2)

## Re: (Score:1)

I'm not trying to justify anything. I'm trying to explain the problem. You're approaching it from a programming point of view. That's the wrong point of view. The prize is being offered for a mathematical proof, not for an algorithm, no matter how clever it might be.

## Re: (Score:1)

Yes, I knew what you meant. But considering that the non-completion problem has a straightforward and known solution, and yet the completion version is the basis for this mathematical prize, I think you are underestimating the relevance of it.

## Re: (Score:2)

It's a math problem. That's how math works

As explained below, I do get your point, but actually there are no maths involved in this specific situation. This is a simple pattern finding/applying which is very difficult or even impossible to be generalise to any other situation (what the maths contributions would be about). Basically, building an algorithm to allow the given piece of software to efficiently perform the expected actions. This is pure software development and algorithm building; a heterogeneous skill requiring knowledge from different

## Re: (Score:2)

considering that the non-completion problem has a straightforward and known solution, and yet the completion version is the basis for this mathematical prize, I think you are underestimating the relevance of it.

I think that, when having a clearly-defined, actually-analysable and punctually-criticisable problem/solution, you should better stick to the given conditions. Having some initial minor prejudices seems as a quite sensible behaviour in these situations ("they offer a lot", "these people seem to know what they are talking about", etc.), but this should be it. Expecting whatever final assessment to be based upon so abstract prejudices is very far from ideal; at least, among (even slightly) knowledgeable and k

## Re: (Score:1)

## Re: (Score:2)

Do you know what "proof" means? I'm giving up on you. It's their problem and their prize. They made the rules. You can't change them just because you want to.

Firstly, "proof" has many meanings and implications depending upon the context. Secondly, having something actually delivering it is the best possible proof of something which anyone could ever come up with (isn't it evident?). And thirdly, you are also misunderstanding the prize/rules/proposers: on one hand, you have the proposers of this specific X-queen problem which aren't offering any money and which only want a proof that said problem can be solved (= delivering an actual solution would be the best pr

## Re: (Score:3)

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, etc. board. Move it over, put it in the same relative location in the 8x8 group at the corner of the larger board, done. So solve for 8x8 and move.

So you'll need to split that money with me, pal. :)

Of course, it's just

slightlypossible that TFS is not an accurate summary of the actual article / problem, but...Nah. Besides, everyone knows that reading TFA is un-American. Even reading the summary raises red flags with Homeland Security, and may result in a National Security Letter (which you can read, but can't discuss.)

You are correct, the article and the summary are misleading/wrong.

Here's those guys explaining the problem and prize again.

https://www.claymath.org/event... [claymath.org]

## Re: (Score:1)

I'm not sure whether or not I understood your "solution", but if I did, I don't think it works quite as easily as you suggest.

What I think you proposed, was dividing the larger board into a grid of sub-grids, and then just filling them in recursively (so, for example, to get a 64x64 solution, start with an 8x8 solution, replace each empty square with an empty 8x8 grid inside of it, and each queen with an 8x8 solution). If that's your method, it doesn't work because the diagonals on the higher order board sp

## Re: (Score:2)

The same could be said about factorizing large integer numbers in encryption or bitcoin mining with 256-bit hashes based on SHA-256. But it's the ratio to the vast combination size relative to the actual available solutions. Universities have a similar challenge in finding a campus wide timetable that guarantees that no student has a set of courses that clash in terms of tutorials/lectures/lab times, but that all students can attend tutorials/lectures/labs that are common to many subjects.

## The story is mis-worded. You did it again editors. (Score:5, Informative)

> Dr Jefferson added: “There is a $1,000,000 prize for anyone who can prove whether or not the Queens Puzzle can be solved quickly so the rewards are high.”

It's not the solution that gets you the prize, but the proof that the solution can be done quickly (without exploring nearly every permutation).

## Re: (Score:3)

Yes it would. The Queen's Puzzle is an NP-complete problem, hence a solution to it would solve every other NP-complete problem.

## Re: The story is mis-worded. You did it again edit (Score:1)

## Re: (Score:2)

More to the point, anything larger that 8x8 isn't a chess board

Well... [wikipedia.org]

## Re: (Score:1)

To slashdot's apparent surprise, once again the article happens to provide the answer. Amazing run of good fortune there.

-- "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.”

## misleading title and rebranded P vs NP (Score:5, Insightful)

Second of all, the $1m prize is exactly the clay millennium prize for the resolution of P vs NP. If n-qeens has a solution in P, being NP-complete, this implies P=NP.

tldr Sensationalist title is sensationalist

## Re: (Score:2)

Moreover, you can write a headline like this every single day and never exhaust the number P vs NP equivalent problems.

How Sudoku could win you a million dollars [unimelb.edu.au]

Finding others is an exercise for the reader.

## Re: (Score:2)

## P=NP is easy to do in Python (Score:2, Offtopic)

I don't understand the fuss, I found not only one but TWO ways to figure out P=NP using Python. Doesn't even require numpy or a GPU and it works even with super big numbers.

#Solution 1:

for N in range(sys.maxsize):

P = 0

if P == N * P:

print("it works.")

#Solution 2:

for P in range(sys.maxsize):

N = 1

if P == N * P:

## Re: (Score:3)

It's not necessarily the issue of P=NP, though such a solution absolutely would resolve this issue.

The "problem" here is that there is no cost function. This is an Ariadne's Thread dilemma in that you can only verify your solution once you have placed as many queens as your placement will allow. You cannot place a single queen on an n x n board and then conclude that you are one step closer to a solution. There is no way to subdivide this problem, hence no way to solve it in a "sufficiently" fast manner (i.

## Re: (Score:2)

## Solve P=NP win $$$ (Score:1)

Also something about chess.

## I solved it (Score:2, Funny)

I have discovered a truly remarkable program which this box is too small to contain. I'll complete it after I get back from a duel I have later today.

## Re: I solved it (Score:2)

## The actual content of the article (Score:4, Informative)

Three researchers proved that the queen problem is NP-complete. The prize is the millennium prize for P=NP. The journal publication is at http://jair.org/papers/paper5512.html.

## Re: (Score:1)

I haven't read the paper, but I have a suspicion that this paper's conclusion that partially-filled N-queens is NP complete will be shown to be false.

Why? Because my gut tells me that you can probably permute the board and convert partially-filled n-queens problem to a "normalized" form that can be solved as efficiently as the empty board n-queens problem: "can this input be rearranged into a prefix substring of the normalized solution for NxN?"

## Re: (Score:1)

Because my gut tells me that you can probably permute the board and convert partially-filled n-queens problem to a "normalized" form that can be solved as efficiently as the empty board n-queens problem: "can this input be rearranged into a prefix substring of the normalized solution for NxN?"

Interesting idea, but JOTTOMH I'm concerned about the normalization step. Permutation grows super-polynomially, of course, so naive normalization won't get you out of NP-Complete.

Or from the other direction: assuming one-way functions exist, then starting with a normal-form partial-N-queens solution, shuffling into any of the non-normal permutations is poly-time, but reversing that shuffle looks at first glance like it might be orthogonal to some other one-way functions.

But that's based on, like, 30 seconds

## Re: (Score:3)

too bad that with Prolog solving the queen problem using CLP(FD) (using gprolog for instance) 500 queens can be solved in less than a second...

The problem is that, as the the paper shows, the n-queen problem is NP-complete, which in layman's terms means that the best algorithm that we know of would take exponential time to solve it.

To illustrate it, let's assume a hypothetical problem that has an (exponential) algorithm which takes 1 second to solve it with an input of 500 (queens or otherwise), and that the base of the exponent is 2 -- meaning that it would take 2 seconds to solve for an input of 501, 4 seconds for an input of 502, and so on.

Cont

## Define "quick" (Score:2)

Serious question... I've written something like that before, and although it wasn't speedy... I don't recall it being particularly long either.

Also, does it have to come up with all solutions quickly, or just one?

## Re: (Score:2)

## Re: (Score:2)

Perhaps you had failed to notice that I had said never mind in the above reply to my own post. I realized what they were talking about after I had already posted the first comment. Slashdot doesn't allow deletion of posts, so....

Clearly I should have paid more attention before posting, but I would have figured that my previous comment would make it obvious that I was aware of that mistake.

Anyways, telling me to shut up after I already admitted my bad is at best only making you look like you are too

## Re: (Score:2)

## Re: (Score:3)

"Quick" is defined in terms of how the running time for the solver scales with the size of the board. If you plot the time it takes to place N queens on an NxN board, you get an exponential curve for all currently known solvers. Either of two possibilities will result in winning $1 million:

1. Proving that this is the best one can do and that there are no better algorithms.

2. Finding a queens-placing algorithm whose running time is bounded by a polynomial function on N.

## Re: (Score:2)

## Re: (Score:2)

onesolution to the n-queens problem, there are constructive algorithms for placing queens on the board that produce one solution (well, four with symmetry) in O(n) operations. Not just polynomial, but linear.## Here's your algorithm (Score:2)

Start cursor in the upper left cell.

Mark/Queen location

--- Subroutine start

Shift cursor right, down 2 (like a Knight!)

Mark

if out of bounds or final Y row

break

--- Subrouting end

Shift cursor up, right 2

Mark

--- Subroutine start

Shift cursor right, up 2

Mark

if out of bounds or initial Y row

break

--- Subrouting end

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)

## Re: (Score:2)

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 mistak

## Re: (Score:2)

## Re: (Score:2)

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

## Re: (Score:2)

I know what his algorithm does. And for n=1000, it will take more time than a billion universes put together. Thus he will get nothing -- at least not in this Universe.

## Re: (Score:2)

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 ho

## Re: (Score:2)

I gotta say this is interesting, but maybe not workable.

Is there a simple algorithm for locating the solved 8x8 into a 10x10 and then placing the remaining 2 queens into the open squares?

We can't know ahead of time what the new location of the solved puzzle will be in the larger puzzle.

We'll have to try all the possible new locations. I doubt it can be guaranteed that if a solution for n exists, then there will be guaranteed a solution for n+1 in which that n solution can be embedded, and that is a requirem

## Re: (Score:2)

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 descript

## Re: (Score:2)

## Re: (Score:2)

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 paren

## Re: (Score:2)

It takes under a second to run this (given a fair bit of memory, since scripting languages are greedy):

$start = microtime();

$n = 1000;

$emptyVal = 0;

$queenVal = 1;

$n_by_n_array = array_fill(0, $n, array_fill(0, $n, $emptyVal));

$xptr = 0;

$yptr = 0;

$queensPlaced = 0;

while(true)

{

$n_by_n_array[$yptr][$xptr] = $queenVal;

$queensPlaced++;

$xptr += 1;

$yptr += 2;

if ($yptr

## Re: (Score:2)

## Re: (Score:2)

I share CustomSolvers2's reserve in your apparent assumption that a technique that works specifically(?) on an 8*8 board would work for larger boards. A simple, and obvious test would be to try it with a 9*9 grid, and eyeball the result - though you'd have to implement some way to view the proposed solution for that board size. I don't even know, does the particular algorithm you're using work for all the smaller board sizes as well? FWIW, I'm a bit ashamed to admit I do not currently understand your code,

## Re: (Score:2)

My solution does not satisfy as a solution for n queens in an n x n board for many different values. Notably, there is no solution for n=4, n=3, n=2.

The problem is deceptively easy for n/2+1 placements. Once past that, it takes an increasingly (maybe infinitely) complex perturbation to get a stable algorithm as size increases. See 8x8 below, where 8/2+1 placements are algorithmically simple.

1 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0 -- 1, ceil(n/2) always a valid placement starting from 0 index

0 1 0 0 0 0 0 0

0 0 0 0 0

## Re: (Score:2)

Thanks.

If you were able to come up with a relatively simple general solution, it's not very hard for a computer to calculate 1mil x 1mil grid (https://www.quora.com/How-many-operations-per-second-can-a-computer-do-How-is-it-related-to-GHz). If you can parallelize this problem (which will do so nicely), the processing time of that experiment won't be noticeable. Proving that it's properly parallelized is another NP problem.

And I tend to agree.

## Where is my Beowulf cluster joke (Score:2)

## Re: (Score:2)

## Re: (Score:1)

with 100M cores in a compute cluster I imagine this problem simplifies into a few months worth of cluster time...

It depends. Do the nodes in the cluster run systemd?

## When will slashdot hit rock bottom? (Score:2)

So, prove P=NP, win $1 million. Makes sense, why is this nonsense even here?

## Visualizer of different algos (Score:3, Interesting)

Really cool in-browser visualizer of 5 different algorithms for solving this problem...

http://haseebq.com/n-queens-visualizer/ [haseebq.com]

## The summary and article are crap (Score:2)

Both the summary and the article are crap.

The important part is the following line from the abstract:

We show that n-Queens Completion is both NP-Complete and #P-Complete.

All the rest (other than the math in the actual paper) is fluff.

## Obviously, (Score:2)

## feels like (Score:2)

## Re: (Score:2)

Complexity of base solution is O(n!). If you think that going possibly 2-3 faster with your favorite toy language compared to java is going to change much for n=1000, you are seriously confused.