## Contest 34: Eight Queens

Online C++ programming contests.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard, raimo

### The code

<pre>
#include <vector>
using namespace std;

// Defines
#define MAX_K 8

void solveboard(const std::vector<short int> &board, std::vector<std::vector<short int> > &solution)
{
int column[MAX_K] = {0, 0, 0, 0, 0, 0, 0, 0};
int row[MAX_K] = {0, 0, 0, 0, 0, 0, 0, 0};
int up_diagonal[2 * MAX_K - 1] = {0, 0, 0, 0, 0, 0, 0, 0};
int down_diagonal[2 * MAX_K - 1] = {0, 0, 0, 0, 0, 0, 0, 0};
int row_exists[MAX_K] = {0, 0, 0, 0, 0, 0, 0, 0};
int x, y, i;

if (board.size() == MAX_K)
{
solution.resize(1);
solution[0].resize(MAX_K);
for (y = 0; y < MAX_K; y++)
solution[0][y] = board[y];
return;
}

for (i = board.size() - 1; i >= 0; i--)
{
y = board[i];
x = y >> 3;
y = y & 7;

if (column[x] || row_exists[y] || up_diagonal[y + x] || down_diagonal[y + MAX_K - x - 1])
return;

row[y] = x; // only need one place to keep track
down_diagonal[y + MAX_K - x - 1] = 1;
up_diagonal[y + x] = 1;
column[x] = 1;
row_exists[y] = 1;
}

x = 0;

// skip all rows filled in before this function was called
for (y = 0; y < MAX_K && row_exists[y]; y++);

while (true)
{
if (x == MAX_K)
{
// skip all rows filled in before this function was called
for (y--; y >= 0 && row_exists[y]; y--);

if (y < 0)
break;

// go down a row
x = row[y];
down_diagonal[y + MAX_K - x - 1] = 0;
up_diagonal[y + x] = 0;
column[x] = 0;
}
else if (!(column[x] || up_diagonal[y + x] || down_diagonal[y + MAX_K - x - 1]))
{
row[y] = x;
if (y + 1 != MAX_K)
{
// go up a row
down_diagonal[y + MAX_K - x - 1] = 1;
up_diagonal[y + x] = 1;
column[x] = 1;

// skip all rows filled in before this function was called
for (y++; y < MAX_K && row_exists[y]; y++);

if (y < MAX_K)
{
x = 0;
continue;
}
}

// found a solution
i = solution.size();
solution.resize(i + 1);
solution[i].resize(MAX_K);
for (y = 0; y < MAX_K; y++)
solution[i][y] = y | (row[y] << 3);

y = MAX_K - 1;

// make it so the row will pop in the next loop
x = MAX_K;
continue;
}
x++;
}
}
</pre>
Nexis

Posts: 10
Joined: Tue Nov 18, 2003 11:59 am

Nexis wrote: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.

Thanks for posting the code, btw.

I think in bigger contests the code will become very messy indeed regardless of the optimizations. It doesn't matter how good the compiler is at optimizing, you are likely to get faster code by making sure the compiler "understands" how the executable should be created.

Another point is that it's always possible that the compiler fails to compile a code correctly with optimizations but not without them(shouldn't be such a big problem with standard c++, though). See what comes on top with keywords "g++ o3" in google. Of course you could use -O,-O2 or whatever. Who decides which of them should be used? I think GCC does some simple optimizing by default when it's absolutely safe.

And then, which of these are a suitable combination of optimizations to you, what do you think:

-march=athlon -falign-functions=2 -falign-jumps=2 -falign-labels=2 -falign-loops=2 -fbounds-check -fcaller-saves -fcprop-registers -fcse-follow-jumps -fcse-skip-blocks -fdata-sections -fdelete-null-pointer-checks -fexpensive-optimizations -ffast-math -ffloat-store -fforce-addr -fforce-mem -ffunction-sections -fgcse -fgcse-lm -fgcse-sm -finline-functions -finline-limit=4 -fkeep-inline-functions -fkeep-static-consts -fmerge-constants -fmerge-all-constants -fmove-all-movables -fno-branch-count-reg -fno-default-inline -fno-defer-pop -fno-function-cse -fno-guess-branch-probability -fno-inline -fno-math-errno -fno-peephole -fno-peephole2 -funsafe-math-optimizations -fno-trapping-math -fomit-frame-pointer -foptimize-register-move -foptimize-sibling-calls -fprefetch-loop-arrays -freduce-all-givs -fregmove -frename-registers -frerun-cse-after-loop -frerun-loop-opt -fschedule-insns -fschedule-insns2 -fno-sched-interblock -fno-sched-spec -fsched-spec-load -fsched-spec-load-dangerous -fsingle-precision-constant -fssa -fssa-ccp -fssa-dce -fstrength-reduce -fstrict-aliasing -fthread-jumps -ftrapv -O3
?

raimo

Posts: 372
Joined: Fri Sep 26, 2003 6:50 am
Location: Finland

I didn't participate in this contest because I thought that lots of people will participate and since it is a simple contest, I wouldn't have a chance.
So I thought that there is no point in taking the time to write a solution.

In the end, it turned out that only 2(!) people participated.
And I had a chance.
And I would have got third place in the worst case!

Next time, I WILL patricipate. And I'm going for third place!

Dudi Hatotah

Posts: 222
Joined: Fri Oct 03, 2003 4:17 pm
Location: Micronesia, the island of Yap

um... how'd you post formatted code without code tags? HTML's not supposed to be allowed to do that.
So when's the next contest?

Wizard
Site Admin

Posts: 3226
Joined: Mon Sep 22, 2003 4:52 pm
Location: ON, CA

He used <pre>-tags instead of [code]-tags, I think.

I have a feeling that the next contest will start as soon as we have come up with something new which interests so much that more participants take part.

raimo

Posts: 372
Joined: Fri Sep 26, 2003 6:50 am
Location: Finland

It seems that I missed this contest entirely.

Looks like we need a new contest idea. Perhaps: given two matrices, determine how many times the second matrix appears as a submatrix of the first. We already have a matrix class (from contest 24).

Beer Hunter

Posts: 912
Joined: Sat Dec 13, 2003 7:12 pm
Location: Australia

Congratulations Nexis!
I really didn't give any challenge to you as everyone can see, and that's because I didn't optimize nearly at all. Sorry for being lazy .
However, it was a nice contest .
egaga

Posts: 7
Joined: Sat Nov 15, 2003 12:34 pm
Location: Finland

The submatrix idea could work. I was thinking that some kind of AI contest would be fun too.

raimo

Posts: 372
Joined: Fri Sep 26, 2003 6:50 am
Location: Finland

What about a resnik cube contest? I think it has a good potential, brute force dosn't work and if you don't do some kind of optimization a solution could take for ever.... Just a sugestion.
Tio America

Posts: 4
Joined: Sat Jun 12, 2004 7:23 pm
Location: Rio De Janeiro, Brazil

Previous

Return to Contests

### Who is online

Users browsing this forum: No registered users and 0 guests