NQueen真的回溯？

Question

NQueen problem是backtracking的着名示例。從source閱讀後，我嘗試了下面的代碼片段。

int isSafe(int k,int i,int *x) 
{ 
    int j; 
    for(j=0;j<k;j++) 
    { 
       //old queen is placed at jth row of x[j] column 
       //new queen to be placed at kth row of ith column 
      if(i==x[j] || abs(k-j)==abs(i-x[j])) 
        return 0; 
    } 
    return 1; 
} 

int Nqueen(int k, int* sol, int N) 
{ 
    int col; 
    if(k == N) 
    { 
      printSol(sol,N); 
      return 1; 
    } 
    else 
    { 
      for(col = 1;col <= N; col++) //determines appropriate column number of the kth queen to be placed 
      { 
        if(isSafe(k,col,sol)) 
        { 
          sol[k] = col; 
          if(Nqueen(k+1, sol, N)) 
            return 1; 
          sol[k] = 0; // backtrack 
        } 
      } 
      return 0; // solution not possible 
    } 
} 

我收到output爲：

1 5 8 6 3 7 2 4 

然而，當我評論這回溯的聲明，我收到相同output沒有任何問題。

int Nqueen(int k, int* sol, int N) 
{ 
    int col; 
    if(k == N) 
    { 
      printSol(sol,N); 
      return 1; 
    } 
    else 
    { 
      for(col = 1;col <= N; col++) //determines appropriate column number of the kth queen to be placed 
      { 
        if(isSafe(k,col,sol)) 
        { 
          sol[k] = col; 
          if(Nqueen(k+1, sol, N)) 
            return 1; 
          // sol[k] = 0; <-------------- Notice this change 
        } 
      } 
      return 0; 
    } 
} 

究竟是什麼導致了NQueen問題，一個回溯的問題？

難道不是一個簡單的遞歸方法嗎？

Answer 1

sol[k] = 0不是回溯部分。回溯是在遞歸調用中完成的：if(Nqueen(k+1, sol, N))。

回溯的想法是一個徹底的搜索 - 你試圖搜索所有的可能性，直到找到一個。在這裏，你正在嘗試董事會所有可能的女王職位分配，並且如果它仍然安全，則繼續「繼續」。如果您發現它不安全，您將從遞歸返回並嘗試下一個選項。

我相信註釋掉的行只能確保如果沒有找到解決方案，結果數組是[0,...,0]，而不是一些無意義的數組。

Answer 2

首先，你真的需要了解算法（這會告訴你評論這些東西並不重要）。正如你所注意到的，這個算法是遞歸的。這是回溯，因爲你

• 設置的第k個皇后的位置
• 探索可能放置的皇后K + 1，K + 2，...
• 然後你回到第k - 女王，把它放在別的地方，並重復

看到，在第3步，我們「回到」第k皇后。這就是我如何解釋自己爲什麼稱爲回溯的原因。

Answer 3

回溯問題是一種編程範例，您可以在其中嘗試每種可能的組合。然後，對於每個組合，您檢查組合是否正確。 下面是N（或8）皇后問題的幾個步驟。

1. 開始從行0和1的地方在女王山口0
2. 現在放置在第1行第2個女王和col 0
3. 檢查，如果位置是安全的
4. 如果沒有安全的地方第二次在女王第1行，列1
5. 也不安全，現在將第二王后在第1行，列2

繼續像這樣通過把女王在每一個每一個可能的列，並檢查是否安全。 您可以省略顯而易見的錯誤情況，就像不會將2個皇后放在同一行中一樣。 下面是我的8皇后問題代碼，打印所有可能的解決方案。

#include<stdio.h> 


int abs(int a){ 
     return a>0? a : -a; 
} 

int isSafe(int col[],int row){ 
     int row2,col2,i,yDiff,xDiff; 
       if(row == 0) return 1; 


    for(row2=0;row2<row;row2++){ 
        if(col[row2] == col[row]) 
          return 0; 

        xDiff = col[row2] - col[row]; 
        xDiff = abs(xDiff); 
        yDiff = row - row2; 
        if(xDiff == yDiff) 
            return 0; 
      } 

    return 1; 

}

int Nqueen(int col[],int n, int row){ 
     int i; 
     if(row==n){ 
       printf("\n"); 
       for(i=0;i<n;i++) 
         printf("%d ",col[i]+1); 

     }else{ 
       for(i=0;i<n;i++){ 
        col[row] = i; 
        if(isSafe(col,row)){ 
          queen(col,n,row+1); 
        } 

      } 
    } 

}

int main(){ 
     int col[8]; 
     queen(col,8,0); 

}