8 Königinnenpuzzle mit rekursiver tiefer Suche

Question

Ich versuche, das Rätsel der 8 Königinnen in C zu lösen. Ich habe Probleme mit der rekursiven Suche. Das Programm soll in einer bestimmten Spalte starten:

execute(tabuleiro,8,0); 

Wo die 8 die Anzahl der Spalten in der Platte ist, und 0 ist der Startspalte.

Das funktioniert, wenn ich bei Spalte 0 beginne. Wenn ich eine andere Spaltennummer an die rekursive Suche sende, zählt das Programm nur zur letzten Spalte. Wenn ich z. B. die Suche aus der Spalte 5 starten möchte, suche ich in den Spalten 5 bis 7 nach dem Code, danach suche ich von 0 bis 4, aber das geht nicht.

Wenn ich dies tun:

execute(tabuleiro,8,3); 

Es in füllt nur die letzten 5 colummns, und kehrt nicht in die Spalte 0 die Lösung zu beenden:

Auch, wie kann Ich wähle die Ausgangsposition für die Dame in diesem Code? Wie ich bereits sagte, wird die Spalte im Code zugewiesen, aber ich bin mir nicht sicher, wie ich die richtige Spalte auswählen soll.

Der Code hat 3 Funktionen: eine ist die Anzeige der Karte, eine zweite um zu prüfen, ob die Bewegung legal ist (also eine Königin greift nicht die andere an), und die letzte eine Königin zu setzen und für die Rest des Vorstands.

#include <stdlib.h> 
#include <windows.h> 
int sol = 0; 
void viewtab(int tab[][8], int N) 
{ 
    int i,j; 
    for(i = 0; i < N; i++) 
    { 
     for(j = 0; j < N; j++) 
     { 

      if(tab[i][j] == 1) 
       printf("R\t"); 
      else 
       printf("-\t"); 
     } 
     printf("\n\n"); 
    } 
    printf("\n\n"); 
    system("pause"); 
    printf("\n"); 
} 
int secury(int tab[][8], int N, int lin, int col) 
{ 
    // this function is to check if the move is secury 
    int i, j; 

    // attack in line 
    for(i = 0; i < N; i++) 
    { 
     if(tab[lin][i] == 1) 
      return 0; 
    } 

    //attack in colune 
    for(i = 0; i < N; i++) 
    { 
     if(tab[i][col] == 1) 
      return 0; 
    } 

    // attack in main diagonal 
    // 
    for(i = lin, j = col; i >= 0 && j >= 0; i--, j--) 
    { 
     if(tab[i][j] == 1) 
      return 0; 
    } 
    for(i = lin, j = col; i < N && j < N; i++, j++) 
    { 
     if(tab[i][j] == 1) 
      return 0; 
    } 

    // attack in main secondary 

    for(i = lin, j = col; i >= 0 && j < N; i--, j++) 
    { 
     if(tab[i][j] == 1) 
      return 0; 
    } 
    for(i = lin, j = col; i < N && j >= 0; i++, j--) 
    { 
     if(tab[i][j] == 1) 
      return 0; 
    } 

    // if arrive here the move is secury and return true 
    return 1; 
} 
void execute(int tab[][8], int N, int col) 
{ 
    int i; 
    if(col == N) 
    { 
     printf("Solution %d ::\n\n", sol + 1); 
     viewtab(tab, N); 
     sol++; 
     return; 
    } 

    for(i = 0; i < N; i++) 
    { 
     // check if is secury to put the queen at that colune 
     if(secury(tab, N, i, col)) 
     { 
      // insert the queen (with 1) 
      tab[i][col] = 1; 

      // call recursive 
      execute(tab, N, col + 1); 

      // remove queen (backtracking) 
      tab[i][col] = 0; 
     } 
    } 
} 
int main() 
{ 
    int i, j, tabuleiro[8][8]; 
    for (i = 0; i < 8; i = i + 1) 
     for (j = 0; j < 8; j = j + 1) tabuleiro[i][j] = 0; 

    execute(tabuleiro,8,0); 

    return 0; 
} 

Answer 1

Die Suche stoppt immer in der rechten Spalte, weil Sie speziell sagen, dass es dort zu stoppen:

void execute(int tab[][8], int N, int col) 
{ 
    int i; 
    if(col == N) 
    { 
     printf("Solution %d ::\n\n", sol + 1); 
     viewtab(tab, N); 
     sol++; 
     return; 
    } 

Schauen Sie sich Ihre Abschlussbedingung: Sie die aktuelle Spalte gegen die höchste Spaltennummer überprüfen, und dort anhalten .

Wenn Sie zu Spalte 0 zurückkehren möchten, müssen Sie Ihre Schleifenlogik ändern. Lassen Sie beispielsweise col N erreichen, an diesem Punkt setzen Sie es auf 0 zurück und lassen Sie es so lange weiterlaufen, bis Sie den ursprünglichen Wert erreicht haben. Eine weitere Möglichkeit ist es, bis die Zählung der platzierten Königinnen N. ist

---

Sie wählen den Anfangspunkt auf die gleiche Weise: Sie können die erste auswählen und Ihre rekursiven Anruf. Wenn dies zu einer Lösung führt, drucken Sie sie aus. Ist dies nicht der Fall, geht Ihr oberster Anruf zur nächsten Zeile (Zeile) des Boards und legt die erste Dame dort hin.

Dies ist bereits in Ihrer Hauptlogik. Stellen Sie nur sicher, dass SecuryTrue zurückgibt, wenn die Platine leer ist, anstatt false oder einen Fehler zu werfen.

Answer 2

A. Sie können die erste Königin bei (0,0) platzieren. B. Und beginnen Sie die Suche auch von (0,0). C. Ich sehe keine Notwendigkeit, nach einem anderen Index zu suchen. Erfolgreich !!