8-Quip-Snippet

Question

Ich habe derzeit Backtracking gelernt und bin beim 8-Queen-Problem festgehalten. Ich benutze eine 8x8-Matrix und ich glaube, ich habe einige Probleme mit der Übergabe der Matrix, die an Funktionen übergeht. Jede Hilfe wäre sehr geschätzt. Jeder würde eine Optimierung in den Code bringen, danke.

Hier ist mein 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;

}

Answer 1

Ihre Matrix muss von 0 bis max-1 iterieren,

dh

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. Ein eklatantes Problem ist die Speicherzuweisung:

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

Angesichts dessen MAX ist 7, beide mallocs zuordnen zu wenig Gedächtnis für die Matrix (sieben Elemente statt acht).

Um ehrlich zu sein, würde ich umbenennen MAX zu SIZE oder ähnliches und ändern Sie alle Ihre Schleifen, um streng weniger als zu verwenden, dh

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

Ich würde argumentieren, dass dies etwas idiomatischer und weniger anfällig für Fehler ist.

2. Ich habe nicht versucht, die Logik zu debuggen (ich denke nicht, dass es fair ist, von uns zu erwarten). Ich habe jedoch das nirgendwo außer in bemerkt main weisen Sie Elemente von zu mat. Für mich deutet dies darauf hin, dass der Code möglicherweise nicht korrekt sein kann.

3. Darüber hinaus kann es nützlich sein zu beobachten, dass in einer gültigen Lösung jede Reihe des Schachbretts genau eine Königin enthält. Dies bedeutet, dass Sie keine 8x8-Matrix benötigen, um die Lösung darzustellen: Ein 8-Elemente-Array von Spaltenpositionen ist.

bearbeiten Als Antwort auf Ihre Frage in den Kommentaren finden Sie hier eine vollständige Python -Implementierung, die den oben genannten Punkt 3 zeigt:

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 muss sowohl in der I- als auch im J-Schleifen mit Größe (...) * (max+1) aufgerufen werden.

Darüber hinaus habe ich, als ich Ihr Programm durchführte mat [ri] [c+j was bewertet MAT [-1] [1 Weil r == 1 und i == 2.

Es scheint also einen logischen Fehler in Ihrer Beschreibung des Antidiagonals der Matrix zu geben.