Contest 34: Eight Queens

[Nexis]

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

[raimo]

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
?

[Dudi Hatotah]

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!

[Wizard]

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?

[raimo]

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.

[Beer Hunter]

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).

[egaga]

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 .

[raimo]

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

[Tio America]

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.