8皇后拼圖與遞歸深搜尋

Question

我想解決C中的8皇后拼圖問題。我遇到了遞歸搜索的問題。該方案被認爲在給定的列開始：

execute(tabuleiro,8,0); 

當圖8是在板中的列數，0是起始列。

這在我從第0列開始工作時。當我發送任何其他列號到遞歸搜索時，程序只計數到最後一列。例如，如果我選擇從第5列開始搜索，則從第5列到第7列的代碼搜索，此後應從0搜索到第4列，但它不會這樣做。

如果我這樣做：

execute(tabuleiro,8,3); 

它填補了只有最後5個colummns，並且不會返回列0完成了解決方案：

另外，如何能我在這段代碼中選擇女王的初始位置？就像我之前說過的那樣，該列是在代碼中分配的，但我不確定如何選擇正確的列。

該代碼有3個功能：一個是顯示板，第二個檢查移動是否合法（因此一個女王不會攻擊另一個女王），最後一個放置一個女王並重復董事會的其餘部分。

#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

搜索總是停在最右邊的列，因爲你明確告訴它停在那裏：

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

看看你的終止條件：您檢查與最大的列數當前列，並停在那裏。

如果你想回到第0列，你必須改變你的循環邏輯。例如，讓col達到N，此時您將其重置爲0，並讓它繼續，直到您達到原始值。另一種方法是將持續到放置皇后的計數N.

---

您可以選擇以同樣的方式初始點：你選擇的第一個，讓你的遞歸調用。如果這最終導致解決方案，您打印它。如果沒有，您的最高級別的通話繼續到董事會的下一行（行），並把第一個女王。

這已經在你的主要邏輯。只要確保secury將返回true當板是空的，而不是false或拋出一個錯誤。

Answer 2

答：您可以將第一張女王放在（0,0）處。 B.從（0,0）開始搜索。 C.我沒有看到任何需要開始尋找其他索引。 成功！