8-Queensスニペット

Question

私は現在バックトラッキングを学んでおり、8クイーンの問題に固執しています。8x8マトリックスを使用しています。マトリックスが関数に渡されることに関していくつかの問題があると思います。誰でもコードに最適化をもたらすでしょう、ありがとう。

これが私のコードです。

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

}

Answer 1

マトリックスは0からmax-1に反復する必要があります。

すなわち

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

Answer 2

1. 一つの明白な問題は、メモリの割り当てです。

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

とすれば MAX 7歳です。両方です mallocs マトリックスにメモリが少なすぎる（8ではなく7つの要素）を割り当てることです。

正直に言うと、名前を変更します MAX に SIZE または似たようなもの、そしてすべてのループを変更して厳格ではない、つまり、

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

私は、これはわずかに慣用的であり、エラーが発生しやすいと主張します。

2. 私は論理をデバッグしようとしていません（私たちがそれをすることを期待するのは公平だとは思いません）。しかし、私はそれ以外はどこにもないことに気づきました main の要素に割り当てますか mat. 。私にとってこれは、コードが正しい可能性がないことを示唆しています。

3. それを超えて、有効なソリューションではチェスボードのすべての列に正確に1つの女王が含まれていることを観察することは有用かもしれません。これは、ソリューションを表すために8x8マトリックスを実際に必要としないことを意味します。8要素の列位置の配列が行われます。

編集 コメントの質問に応えて、上記のポイント3を示す完全なPython実装を次に示します。

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)

Answer 3

mallocは、i-とjループの両方でsizeof（...） *（max+1）で呼び出す必要があります。

さらに、私があなたのプログラムを実行したとき、コードがアクセスしようとしているという事実のために、IN_SCACCHI（...）のアンチディアグ部分でアクセス違反を受けました Mat [ri] [c+j それを評価します マット[-1] [1 なぜなら r == 1 と i == 2.

したがって、マトリックスの抗角質の説明には論理的なエラーがあるようです。