something strange with 8 queen problem

[midra]

Hi!
I have a rare problem...
I made a code that it calculates the number of posibilities of put N queens on a NxN board (I am trying to solve one usaco problem in section 1.1.4)
But the problem is that it works for n<10 but when I make an input of '10' or if I put 5 times the number '9' I get an error and the program closes by itself.
(when I say 5 times number '9' I mean: I write '9' , press Enter, it gives me a result: 352, then the program starts again, so I put '9' again and I press Enter, and in the fifth time I get an error and the program closes by itself.
here is the code, and under the code, an explanation of how it works

Code: Select all

#include <stdio.h>

char board[15][15];
int res,n;

set(int row, int col, int val, int val2){
    int i,j;
    board[row][col]=val;
    for(i=row+1,j=col;i<=n;i++)                
        if(board[i][j]==val2) board[i][j]=val;
    for(i=row+1,j=col+1;i<=n,j<=n;i++,j++)    
       if(board[i][j]==val2) board[i][j]=val;
    for(i=row+1,j=col-1;i<=n,j>=1;i++,j--)    
       if(board[i][j]==val2) board[i][j]=val;
}    

back(int i){
    int j;
    for(j=1;j<=n;j++)
      if(board[i][j]==i){
          board[i][j]=0;
          set(i,j,0,i);
          if(i==1 && j==n) {
              printf("Number of possibilities =%d\n",res);
              main();
          }    
          if(j<n) search(i,j+1);
          else back(i-1);
     }
}    

search(int row, int col){
    int i,j;
    for(i=row;i<=n;i++){
       for(j=col;j<=n;j++){
          if(board[i][j]==0){
             if(i==n) res++;
             else{
                 set(i,j,i,0);
                 break;
             }
          }
          if(j==n) back(i-1);
       }    
       col=1;
       
    }
}
int main()
{
  res=0;
  scanf("%d",&n);
  search(1,1);
  return 0;
}

What I suppouse my code do, is:
read an N
then search(1,1) it tells that positionate the 1st queen in row 1 and column 1
in the function search, it starts in the row and column that it gets in the "row" and "col" values and if board[row][col]==0 then it puts a queen there and it calls the attack function, what this function makes is just put the number "row" in all the positions that the queen attacks, when I say the number "row" I mean that it puts the number of the row in all positions that this queen is attacking
for example: first the table is empty:( I am gonna simulate it in 4x4 board)
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
then it looks in row 1 and column 1 and it is 0 so we get:
1 0 0 0
1 1 0 0
1 0 1 0
1 0 0 1
then it changes the row and search in the second row for a position with 0 and then we have:
1 0 0 0
1 1 2 0
1 2 1 2
1 0 2 1
and so on....
then when there is no 0 in a row it goes back with the funcion back(i-1) that it just go one step before
well I don't know why it gives me an error with the value 10
I don't know what else I can explain...
if someone wants to help me I would appreciate very very much!
I really was a lot of hours trying to debug this error but I can't see what's wrong
if someone doesn't understand anypart please ask me
and one more question...
is it ineficient the way I get the solutions

[misof]

Didn't read it all, but this caught my eye:

Code: Select all

for(i=row+1,j=col-1;i<=n,j>=1;i++,j--)    

Isn't it supposed to be

Code: Select all

for(i=row+1,j=col-1;i<=n && j>=1;i++,j--)    

(There are more cases like this in your code.)

IMHO the comma operator evaluates both sides sequentially (first the left side, then the right side) and returns what the right side returns.
E.g. after the command y=(x=2,x=3); both x and y will equal 3. Similarly, your condition is equivalent to j>=1 and it may lead to some overflow.

Some unintended illegal memory access is most probably the problem you seek.

[midra]

thank you so much! I didn't know that
I change my code in this parts.
But I still got the same error

Code: Select all

#include <stdio.h>

char board[15][15];
int res,n;

set(int row, int col, int val, int val2){
    int i,j;
    board[row][col]=val;
    for(i=row+1,j=col;i<=n;i++)                
        if(board[i][j]==val2) board[i][j]=val;
    for(i=row+1,j=col+1;i<=n && j<=n;i++,j++)   
       if(board[i][j]==val2) board[i][j]=val;
    for(i=row+1,j=col-1;i<=n && j>=1;i++,j--)   
       if(board[i][j]==val2) board[i][j]=val;
}    

back(int i){
    int j;
    for(j=1;j<=n;j++)
      if(board[i][j]==i){
          board[i][j]=0;
          set(i,j,0,i);
          if(i==1 && j==n) {
              printf("Number of possibilities =%d\n",res);
              main();
          }    
          if(j<n) search(i,j+1);
          else back(i-1);
     }
}    

search(int row, int col){
    int i,j;
    for(i=row;i<=n;i++){
       for(j=col;j<=n;j++){
          if(board[i][j]==0){
             if(i==n) res++;
             else{
                 set(i,j,i,0);
                 break;
             }
          }
          if(j==n) back(i-1);
       }    
       col=1;
       
    }
}

int main()
{
  res=0;int i,j;
  scanf("%d",&n);
  search(1,1);
  return 0;
}

I just change this part...but it seems there has more bugs
but thanks again!

[Alessandro]

This kind of errors are born when you forget to reset some variable. I didn't read the code (I'm tired now ^_^) but try to check for it.

But excuse me, can't you write plainer code? I think it's not a good habit to merge two loop in one. *Almost* all the problems I did were straightforward to write, so I don't think you need to compress the code. I solved that problem at USACO with a simple program ^_^

Ciao
Ale

[midra]

ok...I have recode it all and make it in a different way...
but this time, it works perfectly in my computer but not for the judge!
I just can't understand...

Code: Select all

/*
 ID: XXX
 TASK: checker
 LANG: C
*/

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

FILE *in,*out;

enum bool {FALSE,TRUE};
typedef enum bool boolean;
int col[15],n,t=0,res=0;

search(boolean *s,int i,boolean row[],boolean diag1[],boolean diag2[]){
	int j=1,k;
	*s=FALSE;
	while(j<=n && !*s){
		if(row[j] && diag1[i+j-1] && diag2[n+j-i]){
           col[i]=j;
           if(i<n){
             row[j]=diag1[i+j-1]=diag2[n+j-i]=FALSE;
             search(s,i+1,row,diag1,diag2);
             if(!*s)
			   row[j]=diag1[i+j-1]=diag2[n+j-i]=TRUE;
		   }
		   else {
		        if(t<3){
     				for(k=1;k<n;k++) 
		    	       fprintf(out,"%d ",col[k]);
			           fprintf(out,"%d\n",col[n]);
			           t++;
					}
					res++;
			    *s=FALSE;
		   }
	    }
		j++;
	}
}

init(boolean row[],boolean diag1[],boolean diag2[]){
	int i,j=2*n;
	for(i=1;i<j;i++) diag1[i]=diag2[i]=TRUE;
	for(i=1;i<n;i++) row[i]=TRUE;
}

int main()
{
   boolean row[15],diag1[27],diag2[27],s;
   int i;
   in=fopen("checker.in","r");
   out=fopen("checker.out","w");
   fscanf(in,"%d",&n);
   init(row,diag1,diag2);
   search(&s,1,row,diag1,diag2);
   fprintf(out,"%d\n",res);
   exit (0);
}

When I compile in Dev-cpp it works perfectly for all the tests, but when I send it to the usaco judge it says that for the test '10' my program outputs '0'
WHY???
Am I never be able to solve this problem?????? I can't believe that the same problem that seems to be not so hard is giving me so much problems

thanks anyway!
bye!!!