Small difference when compiled with gcc and g++

drigz · 07-27-2004, 09:56 AM

I have written an nqueens program in C, but I am trying to submit it to the USACO testing program (http://ace.delos.com/usacogate) which compiles with g++. Here is the code:

Code:

#include <stdio.h>
#include <stdlib.h>

int nqueens, sols;
int rows[13];
int pos[(13*2)-1];
int neg[(13*2)-1];
FILE *fin, *fout;

int isValid(int col, int row)
{
int i;
for(i=0;i<nqueens;i++)
if(rows[i]==col) return 0;
if(pos[col+row-1]) return 0;
if(neg[row+nqueens-col]) return 0;
return 1;
}

int printBoard()
{
int i;
sols++;
if(sols<4)
{
for(i=0;i<nqueens-1;i++)
fprintf(fout, "%d ", rows[i]+1);
fprintf(fout, "%d\n", rows[nqueens-1]+1);
}
}

int search(int row)
{
int i;
for(i=0;i<nqueens;i++)
if(isValid(i,row))
{
rows[row]=i;
pos[i+row-1]=1;
neg[nqueens+row-i]=1;
if(row==(nqueens-1)) printBoard(); else search(row+1);
rows[row]=-1;
pos[i+row-1]=0;
neg[nqueens+row-i]=0;
}
}

int main()
{
int i;
sols=0;
char inn[3];

fin=fopen("checker.in","r");
fout=fopen("checker.out","w");

fgets(inn,sizeof(inn),fin);
nqueens=atoi(inn);
fclose(fin);

for(i=0;i<nqueens;i++)
rows[i]=-1;
for(i=0;i<(nqueens*2)-1;i++)
pos[i]=neg[i]=0;

search(0);
fprintf(fout, "%d\n",sols);
fclose(fout);
}

when compiled with gcc, this works perfectly with inputs (for checker.in) up to 13. However, if you use g++, then it only works up to 12, and the output for 13 is wrong:
correct output for 13:

Code:

1 3 5 2 9 12 10 13 4 6 8 11 7
1 3 5 7 9 11 13 2 4 6 8 10 12
1 3 5 7 12 10 13 6 4 2 8 11 9
73712

g++ output for 13:

Code:

1 3 5 2 9 12 10 13 4 6 8 11 7
1 3 5 7 9 11 13 2 4 6 8 10 12
1 3 5 7 12 10 13 6 4 2 8 11 9
70952

What could have caused this error, and how can I fix it?

drigz · 07-28-2004, 04:26 PM

I still don't have any idea what might cause this, and I don't want to risk losing my membership by changing it to add a bit to the answer if its 13...but I don't want such a stupid problem to be stopping me from progressing.

AltF4 · 07-28-2004, 09:08 PM

If you access element 13 of your array you access outside your defined array boundary

int rows[13]; // allocates 13 elements rows[0] .... rows[12]

rows[13] accesses some random memory outside "rows" and the result is "undefined behaviour"

different compilers act differently on "undefined behaviour" :-)

drigz · 07-29-2004, 07:59 AM

i thought it would be fine because i was only using rows 0 to 12, but it seemed to fix it, so thanks.

AltF4 · 07-30-2004, 06:49 PM

no problem :-)

cillm527 · 06-15-2006, 04:09 PM

The infamous USACO queens problem. Congrats for solving it. But you might want to remove the code, as that could get you into trouble.