Last visit was: It is currently Thu Mar 28, 2024 4:53 am


All times are UTC-05:00




Post new topic Reply to topic  [64 posts ] 
Author Message
 Post subject:Challenge Two: N-Queens
PostPosted:Thu Aug 09, 2007 2:41 am 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
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):
Code:
0 # of solutions for 2 x 2 = 0 0 # of solutions for 3 x 3 = 0 0 # of solutions for 4 x 4 = 2 0 # of solutions for 5 x 5 = 10 0 # of solutions for 6 x 6 = 4 0 # of solutions for 7 x 7 = 40 0 # of solutions for 8 x 8 = 92 0 # of solutions for 9 x 9 = 352 31 # of solutions for 10 x 10 = 724 281 # of solutions for 11 x 11 = 2680 2765 # of solutions for 12 x 12 = 14200
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

Image


Last edited by Tycho on Tue Sep 04, 2007 3:25 pm, edited 1 time in total.

Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 7:29 am 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
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.


Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 8:28 am 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
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


Last edited by Gwanky on Thu Aug 09, 2007 11:03 am, edited 1 time in total.

Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 9:15 am 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
Also there's nothing involving C# with onlink is there? Because I am much more proficient in that. (Sorry for tripple post)


Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 9:43 am 
User avatar
 

Joined:Sat Mar 11, 2006 8:28 am
Posts:365
Location:Canada
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

_________________
Best file compression around: "DEL *.*" = 100% compression
"640K ought to be enough for anybody." - Bill Gates, 1981


Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 10:35 am 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
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.


Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 11:40 am 
User avatar
 

Joined:Sat Mar 11, 2006 8:28 am
Posts:365
Location:Canada
*Shrug*

_________________
Best file compression around: "DEL *.*" = 100% compression
"640K ought to be enough for anybody." - Bill Gates, 1981


Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 1:56 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
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. :)

_________________
- Tycho

Image


Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 2:11 pm 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
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.


Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 2:40 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Quote:
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.

_________________
- Tycho

Image


Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 3:33 pm 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
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. :(


Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 3:38 pm 
 

Joined:Mon Jul 03, 2006 7:02 am
Posts:16
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)

_________________
Freiheit statt Angst -- Stoppt den Ueberwachungswahn!
Bundesweiter Aktionstag 30.05.2008
www.freiheitstattangst.de
Petition unterzeichen

Please forgive me my poor english, I'm learning it everyday more and more.


Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 4:13 pm 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
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.


Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 5:34 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
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:
Code:
Precalculating 4096 primes... DONE (0.002631 seconds) Finding 1000000 primes using 1 threads... DONE (5.230349 seconds) Finding 1000000 primes using 2 threads... DONE (2.696804 seconds) Finding 1000000 primes using 4 threads... DONE (2.692789 seconds) Finding 1000000 primes using 8 threads... DONE (2.684971 seconds) Finding 1000000 primes using 16 threads... DONE (2.688693 seconds) Finding 1000000 primes using 32 threads... DONE (2.711428 seconds) Finding 1000000 primes using 64 threads... DONE (2.912779 seconds) TOTAL: 21.620443 seconds.
Linux does slightly worse with more than 2 threads, but you get the idea.

_________________
- Tycho

Image


Top
Offline  
 Post subject:
PostPosted:Thu Aug 09, 2007 6:11 pm 
 

Joined:Sun Jun 10, 2007 11:41 am
Posts:344
Location:Ninjaville
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.


Top
Offline  
Display posts from previous: Sort by 
Post new topic Reply to topic

All times are UTC-05:00


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Theme created by Miah with assistance from hyprnova