1

私は現在バックトラッキングを学んでいて、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;

}
4

3 に答える 3

2

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

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

これが 7 であることを考えるとMAX、どちらmallocsもマトリックスに割り当てるメモリが少なすぎます (8 ではなく 7 要素)。

正直なところ、名前を変更MAXするSIZEか、似たようなものにして、すべてのループを厳密な未満を使用するように変更します。つまり、

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

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

2.ロジックのデバッグは試みていません (デバッグを期待するのは適切ではないと思います)。mainただし、の要素に割り当てるのは以外ではどこにもないことに気付きましたmat。私にとって、これはコードが正しいとは言えないことを示唆しています。

3.さらに、有効な解では、チェス盤のすべての列にちょうど 1 つのクイーンが含まれていることを観察すると役立つ場合があります。これは、解を表すために実際には 8x8 行列が必要ないことを意味します。列位置の 8 要素配列で十分です。

editコメントでの質問への回答として、上記のポイント 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)
于 2011-09-05T15:56:03.873 に答える
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;
      }                        
   }
于 2011-09-05T15:55:47.780 に答える
0

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

さらに、あなたのプログラムを実行すると、コードがmat[ri][c+j]にアクセスしようとするため、in_scacchi(...) の antidiag 部分でアクセス違反が発生しました。これはmat[-1]に評価されます。 [1] r==1およびi==2のため。

したがって、行列の反対角の説明に論理的な誤りがあるようです。

于 2011-09-05T16:34:33.130 に答える