8-Queens snippet

Question

I have currently learning backtracking and got stuck on the 8-queen problem, I am using a 8x8 matrix and I think I've got some problems regarding the matrix passing to functions, any help would be highly apreciated.I wouldn't mind if anyone would bring any optimisation to the code, thanks.

here is my code.

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

#define MAX 7



//void azzera(int **mat);
void posiziona(int **mat, int r,int c);
void stampa(int **mat);
int in_scacchi(int **mat,int r ,int c);

int main(int argc, char *argv[])
{



  int i=0,j=0;


  int **mat=(int **)malloc(sizeof(int *)*MAX);
  for(i=0;i<=MAX;i++){
      mat[i]=(int *)malloc(MAX*sizeof(int));               
      for(j=0;j<=MAX;j++){

           mat[i][j]=-1;
      }                        
   }


  printf("insert pos of the first queen on the first row (1-8) :");
  scanf("%d",&i);
  i-=1;
  mat[0][i]=1;

  posiziona(mat,1,0);
  stampa(mat); 

  system("PAUSE");  
  return 0;
}

/*void azzera(int **mat){

  int i=0,j=0;

  for(i=0;i<=MAX;i++){
      for(j=0;j<=MAX;j++){
           mat[i][j]=-1;
      }                        
   }

}*/

void stampa(int **mat){
     int i,j;

     for(i=0;i<=MAX;i++){
      for(j=0;j<=MAX;j++){
           printf(" %d",mat[i][j]);
      }
      printf("\n");                        
   }

}
void posiziona(int **mat, int r,int c){
    int i=0,riga=1,flag_col=-1,flag_riga=-1; 

    if(riga<=7&&flag_riga!=1){

         if(flag_riga==1){
             flag_riga=-1;                 
             posiziona(mat,r+1,0);
         }
         else if(in_scacchi(mat,r,c)==1){
                   if(c==MAX)
                       posiziona(mat,r-1,0);
                   posiziona(mat,r,c+1);  
         }
         else{
                   flag_riga=1;
         }
    }  
}

int in_scacchi(int **mat,int r ,int c){
    int i,j,k,m;
    int flag=0;   
   //col  
   for(i=0;i<r;i++){                 
      for(j=0;j<=c;j++){
           if(((mat[i][j]==1)&&(c==j))) 
                return 1;   

      }                          
   }
   //diag \
   for(i=0;i<MAX-r;i++){                 
      for(j=0;j<=MAX-c;j++){
           if(mat[MAX-r-i][MAX-c-j]==1) 
                return 1;   
      }                     
   }                          

   //antidiag 

   for(i=r+1;i<=MAX;i++){                 
      for(j=c+1;j<=MAX;j++){
           if(mat[r-i][c+j]==1) {
                return 1;   
           }                     
      }                          
   }
   return 0;

}

Note: 8-Queens problem can be solved with out passing matrix to recursion function — TheHorse, Sep 05 '11 at 15:52
@user786653 - Erm, it does considering computers generally think of series as being zero based — Brian Roach, Sep 05 '11 at 15:52
In c typecasting of malloc is implicit and it is not appreciated to to do it explicitly. — Muthu Ganapathy Nathan, Sep 05 '11 at 15:52
@Brian Roach: True, but `malloc(MAX*sizeof(int))` surely ain't right. — NPE, Sep 05 '11 at 15:54
@Brian Roach refer here http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc — Muthu Ganapathy Nathan, Sep 05 '11 at 15:58
@EAGER - it was a joke. Some of us starting writing C before you could do that ;) — Brian Roach, Sep 05 '11 at 15:59
still i'm missing two aspects 1 regarding the passing of the matrix to functions, should I use *** in the declaration and &matrix when being called ? and when i cycle the diagonals of an nxn matrix what is the best way ? (i've found 1 cycle(smallest var) should be ok) — Lucian Enache, Sep 05 '11 at 19:06

NPE · Answer 1 · 2011-09-06T16:46:04.230

1. One glaring problem is the memory allocation:

  int **mat=(int **)malloc(sizeof(int *)*MAX);
  for(i=0;i<=MAX;i++){
      mat[i]=(int *)malloc(MAX*sizeof(int));

Given that MAX is 7, both mallocs are allocating too little memory for the matrix (seven elements instead of eight).

To be honest, I'd rename MAX to SIZE or something similar, and change all your loops to use strict less-than, i.e.

for(i = 0; i < SIZE; i++) {

I would argue that this is slightly more idiomatic and less prone to errors.

2. I haven't tried to debug the logic (I don't think it's fair to expect us to do that). However, I have noticed that nowhere except in main do you assign to elements of mat. To me this suggests that the code can't possibly be correct.

3. Beyond that, it may be useful to observe that in a valid solution every row of the chessboard contains exactly one queen. This means that you don't really need an 8x8 matrix to represent the solution: an 8-element array of column positions will do.

edit In response to your question in the comments, here is a complete Python implementation demonstrating point 3 above:

def can_place(col_positions, col):
  row = len(col_positions)
  for r, c in enumerate(col_positions):
    if c == col or abs(c - col) == abs(r - row): return False
  return True

def queens(n, col_positions = []):
  if len(col_positions) >= n:
    pretty_print(n, col_positions)
    return True
  for col in xrange(n):
    if can_place(col_positions, col):
      if queens(n, col_positions + [col]):
        return True
  return False

def pretty_print(n, col_positions):
  for col in col_positions:
    print '.' * col + 'X' + '.' * (n - 1 - col)

queens(8)

thx got it fixed, still i've got an issue left with the matrix when i pass it by reference should i put *** inside the functions and call the matrix in main with & in front ? — Lucian Enache, Sep 05 '11 at 18:19
@Lucian Enache: It's hard to say what the remaining issue is, but going from a double pointer to a triple pointer will almost certainly **not** fix it. — NPE, Sep 05 '11 at 19:06
so do you think that my approach to use a matrix was wrong and instead I should rely on arrays ? — Lucian Enache, Sep 05 '11 at 19:12
@Lucian Enache: I don't think it's wrong, but I do think it's unnecessarily complicated. — NPE, Sep 06 '11 at 07:08
@Lucian Enache: I'd do just what I said in my answer. I've now edited the answer to add a complete implementation that demonstrates the data structures I was talking about. It's done in a different programming language so as not to interfere with your learning experience. — NPE, Sep 06 '11 at 14:25

score 1 · Accepted Answer · answered Sep 05 '11 at 15:55

Your matrix must iterate from 0 to MAX-1,

i.e

int **mat=  malloc(sizeof(int *)*MAX);
  for(i=0;i< MAX;i++){  //see for i<MAX
      mat[i]=  malloc(MAX*sizeof(int));               
      for(j=0;j<MAX;j++){ //see for j<MAX

           mat[i][j]=-1;
      }                        
   }

chessweb · Answer 3 · 2011-09-05T16:57:03.403

0

malloc must be called with sizeof(...) * (MAX+1) in both the i- and j-loop.

Moreover, when I ran your program I got an access violation in the antidiag portion of in_scacchi(...) due to the fact that the code tries to access mat[r-i][c+j] which evaluates to mat[-1][1] because r==1 and i==2.

So there seems to be a logical error in your description of the anti-diagonal of the matrix.

edited Sep 05 '11 at 16:57

answered Sep 05 '11 at 16:34

chessweb

4,613
5
27
32

Memory allocation is certainly a problem (but clearly isn't the only problem). – NPE Sep 05 '11 at 16:50
@aix: you are right. malloc must be called with sizeof(int)*(MAX+1) – chessweb Sep 05 '11 at 16:51

8-Queens snippet

3 Answers3