Contest 34: Eight Queens

[Nexis]

Well since I already had a queens solution that I wrote in a CS class I decided to modify it to meet the contest specs and see what I could get.

Some preliminary tests averaged over 1000 runs

Empty board: 495,086 and 92 solutions

board with piece(0,1): 64,687 and 8 solutions

board with piece(2,0): 78,619 and 16 solutions

board with piece(2,0) and (7,3): 15,740 and 4 solutions

board with pieces (0,4), (1,2), (2,0), (3,6), (4,1), (5,7), (6,5), (7,3): 1508 and 1 solution

board with pieces (0,4), (1,2), (2,0), (3,6), (4,1), (5,7), (6,5), (7,1): 240 and 0 solutions

board with pieces (0,3), (5,5), (1,2): 225 and 0 solutions

[jgbauman]

Some preliminary tests averaged over 1000 runs

Which hardware (processor/MHz)?
Which compiler?
Did you turn on compiler optimizations?
Those numbers are CPU clock cycles?

The answers would make your numbers more comparable.

[Nexis]

Which hardware (processor/MHz)? Athlon 1700
Which compiler? Visual C++ 7.0
Did you turn on compiler optimizations? used release version
Those numbers are CPU clock cycles? yes

[gamma]

Hi,

Suggestion for advanced contest:
Solve 8queens (or n-queens) at compile time (See also contest 33.)

[Wizard]

oh hey, just realized the deadline passed. How many people entered, as I completely forgot.

[raimo]

It seems that we have two(2) solutions.

Perhaps the reason for unpopularity is that people weren't sure if there's going to be an advanced contest(I'm still not sure. Probably everybody wants something new already) or maybe the forum scared the unregistered people away.

The solution space was small but maybe the problem itself isn't so straight-forward to solve for beginners.

[egaga]

Whoever the second competitor was, I'm sure he/she's got faster solution than mine is. I noticed what improvements I could have done, but I was a bit too lazy and thought that the important thing was I did something. I mean, I needed some exercise.
A big thanks to raimo for this contest. I hope there will be more of them soon!

[Nexis]

Actually the number of contest participants dwindled down a long time ago, after contest 31 or 32 (I can't remember which). Part of the reason was because that contest testing wasn't conducted correctly (and nobody ever fixed it) and the other part because nobody knows about this contest because it's infrequently updated and there's no schedule.

For me, this site offers nothing of interest to me besides an occasional contest. The content on this site is aimed largely at beginners which I am not. Also, the infrequent updates of the site has left me with a dislike of the site itself. I don't even bother visiting the front page anymore and simply bookmark this forum and visit it occasionally.

If you want to get a lot of people interested I think you're going to have to come up with at least one creative contest and then get it posted on a few other sites (I saw the first contest I participated in on gamedev.net myself). However, hosting the contest in a forum won't likely help any due to appearances.

And egaga, I was the other participant. Like I said earlier though, I just did a few modifications to my existing code from a long time ago and submitted it. There were a few things I could have done to make it faster but it was quite fast already (didn't even use any recursion).

[jgbauman]

I have a nearly working (needs just two top-level ifs for a special case) solution for general n's. But I hadn't much time and didn't finish it.

[raimo]

It's true that the content of the site doesn't attract people who are interested in participating programming contests. On the other hand, searching "c++ programming contest" in google brings the site to the top. If I recall correctly, I found this site through a link informing about programming contests.

[loobian]

Reading at Nexis' post, I can only say that I am sorry that this happened to the site. The reason is simple- I have no time for the site anymore. When I created it, I had plenty of free time- not much classes not to talk about work. Things changed though. This is my last year in high school, and I must do excellent in order to be accepted in University.
Also, I am working a lot, in order to do for a living.
So, no more time for the site.
I would have had the time, if the site was better organized via scripts that ease the work on it, but when I created it, I didn't have that knowledge and experience to do it so.
Anyway, if one day I have more time, I may start working hard on the site again...or if people want to work on it, I will let them, as long as I can trust them.

[Jetru]

First, I was the guy who asked how to do this stuff some time ago. Second, the chess board is represented by letters for rows and numbers for columns.Third, I dont understand anything about vectors and all. Fourth, hopefully someone has a solution i can understand.....

[exomo]

Hi everybody.

I couldn't take part this time, I was too lazy .

But I will take part in the next contest (if it isn't too hard)

[raimo]

Btw, I ran the codes for some time ago. The test cases cover at least three different special cases even though they seem quite unimaginary.

Input vectors used

1. {}
2. {3}
3. {4,63}
4. {55,59}
5. {21,38}

Minimum CPU cycles on each test case(solutions were correct):
[FreeBSD 5.1 AMD Athlon 1,3GHz GCC 3.3 without optimizations]

egaga

1. 7747608
2. 943312
3. 141650
4. 182001
5. 238796

Nexis

1. 967129
2. 174290
3. 17553
4. 31324
5. 25441

So I'd say Nexis's code is more efficient. I think there's not much difference in complexity, though.

[Nexis]

In future contests I really think you should turn on compiler optimizations, otherwise the code entered is liable to get even messier since one can't count on the compiler to do simple optimizations. If you're not going to enable optimizations then you should at least specify that in the contest info. Of course this is a moot point unless the contest participation goes up.

Anyways, I'll post the code later if raimo doesn't for anyone interested.