This time, you're going to be trying to write an N-Queens solver. This is another exercise in algorithm design and optimization, this time in both speed and memory usage.

You may not be familiar with the N-Queens problem. I suggest you Google it, among other things. One of the best resources is Wikipedia, of course.

So the main goal is this: find the number of distinct solutions to N queens problems (for example, on an 8x8 board, there are 92 distinct solutions), for N-values of 1 through 14 (and higher if possible). The difference between a 'unique' and 'distinct' solution is cited on that Wikipedia page linked above. Extra points will be given for finding the number of unique solutions in a timely manner. You will be scored on whether the output answer is correct, the time taken (relative to my own solution), code style, etc.

Example output (the first number is the number of milliseconds since the start of the app): The example cited above is a poorly optimized implementation, relative to the world record implementation and Jeff Somers' implementation.

You should write a full program, and when you post it, either upload a RAR somewhere or post the entire code (with #include's, a main() function, and whatever other functions you write).

I haven't yet worked out a scoring system, but it will be a bit harder this time. There will be points deducted for each change that needs to be made to make the function compile, and any changes that need to make the program produce the correct output. Only final submissions (the most recent post by any given submitter) will be graded, so you have plenty of time to perfect your code.

EDITED: This challenge will end on someday. I'm waiting until we have a reasonable number of submissions to grade based on. Great so far, but keep going.

Good luck, everyone. If you need any more information to get started, please reply to this thread and ask any questions you need to!

Tycho do you have an SSE2 CPU? Because if so I will optimize my code to run on sse2. Also do you have a dual core CPU because if so I will add another string.

I'm not sure if this is exactly what you wanted but it is fast and efficient.

http://www.wikiupload.com/download_page.php?id=194927

Its also only 40kb.

This one is more optimized but requires a Pentium 4, Core 2 Duo, Core , Athlon 64 or VIA C7 CPU.

http://www.wikiupload.com/download_page.php?id=195017

Also there's nothing involving C# with onlink is there? Because I am much more proficient in that. (Sorry for tripple post)

Why don't you just edit your old post, and Tycho must have a SEE2 enabled CPU if he made the SSE2 version of Onlink

My bad about the triple post. Also Tycho might not have an SSE2 CPU, as you can still compile it on a machine that doesn't have the instructions.

*Shrug*

I have a MacBook Pro with a Core 2 Duo. I can support up to SSE3 and SSSE3 (Supplemental SSE 3, formerly unofficially and incorrectly referred to as SSE4).

And that's sort of what I was looking for. I was more hoping just for a count of the number of solutions for a given NxN board with N queens. The time it takes to get this count is the critical part.

Well the computer I'm working on is an older P4 so the only above average instruction set I have is SSE2. Also I forgot to mention it will display all possible solutions with no user input if you enter the number of rows then space, then Y. I'm working on another iteration that will be almost twice as fast, if it's important I can rewrite the output, but even if mine is more detailed you still get the information right?

Edit:I didn't realize how much of a bitch multithreading is in C++ as aposed to C#. This might take a while but soon I'll have anything with HT or anything dual core running almost twice as fast.

Funny, I thought the opposite. C# is painful. Hence why it's... you know. Sharp.

I like the humor. C# is harder but C++ doesn't really have support for multithreading for the sake of simplicity. There's ways around it but it's a bitch.

Well, I don't want a flamewar because, its very off-topic, but I have to statement that C# thingy. I like programming in C#, but there is not a really good platform independence (yet). Mono is just what it is, it would never be the same than .Net, because these guys (who doing a very good job, of course) will ever code a stupid clone to support on the other platforms this, what MS does on windows.

But Tycho, programming in C# is as easy/hard as in C++, the imho only thing that C# can do better is type saved coding.

But thats off-topic, so lets discuss this on another place (General hopefully)

Wahoo this one is very optimized and requires a Dual Core CPU, and SSE2.

http://www.wikiupload.com/download_page.php?id=195212

The code is also optimized for windows (it will run faster if compiled into a windows.exe instead of a mac or linux executable).

If your interested I could spend the next couple of days creating a dual core version of onlink. Because of how complex Onlink is I doubt it will scale as well as one of these more simple programs but it certianly can't hurt.

P.S. This version runs runs almost twice as fast as my frist one on a single CPU machine, on a dual core machine it should fly.

There's no doubt that multithreading increases speed. Take the primality thing for example. I wrote a threaded version of it to see how fast it could be when multithreaded on a dual core machine. Here's the output:
Linux does slightly worse with more than 2 threads, but you get the idea.

Hmm I could just be stupid but I can't seem to find Onlink's source anywhere. If you give me access to the source I can have a rudimentery multi threaded build out by tommorow.