N皇后拼圖 - 這個解決方案中的回溯在哪裏？

在研究著名的N Queens puzzle，我碰到this簡單，易於理解的C實現：N皇后拼圖 - 這個解決方案中的回溯在哪裏？

#include<stdio.h> 
#include<math.h> 

int board[20],count; 

int main() 
{ 
int n,i,j; 
void queen(int row,int n); 

printf(" - N Queens Problem Using Backtracking -"); 
printf("\n\nEnter number of Queens:"); 
scanf("%d",&n); 
queen(1,n); 
return 0; 
} 

//function for printing the solution 
void print(int n) 
{ 
int i,j; 
printf("\n\nSolution %d:\n\n",++count); 

for(i=1;i<=n;++i) 
    printf("\t%d",i); 

for(i=1;i<=n;++i) 
{ 
    printf("\n\n%d",i); 
    for(j=1;j<=n;++j) //for nxn board 
    { 
    if(board[i]==j) 
    printf("\tQ"); //queen at i,j position 
    else 
    printf("\t-"); //empty slot 
    } 
} 
} 

/*funtion to check conflicts 
If no conflict for desired postion returns 1 otherwise returns 0*/ 
int place(int row,int column) 
{ 
int i; 
for(i=1;i<=row-1;++i) 
{ 
    //checking column and digonal conflicts 
    if(board[i]==column) 
    return 0; 
    else 
    if(abs(board[i]-column)==abs(i-row)) 
    return 0; 
} 

return 1; //no conflicts 
} 

//function to check for proper positioning of queen 
void queen(int row,int n) 
{ 
int column; 
for(column=1;column<=n;++column) 
{ 
    if(place(row,column)) 
    { 
    board[row]=column; //no conflicts so place queen 
    if(row==n) //dead end 
    print(n); //printing the board configuration 
    else //try queen with next position 
    queen(row+1,n); 
    } 
} 
}

然而，儘管大多數的它看起來正確的給我，我不能看到在回溯它。我錯過了什麼？

在我看來，在queen()函數中，在for循環之後應該檢查是否搜索用盡了沒有成功的特定行/皇后，如果是的話，通過簡單地調用自己的第1行。這個假設是否正確？

來源

2015-11-24 Jay Souper

讓我們深入瞭解一下這個代碼：

void queen(int row,int n) 
{ 
int column; 
for(column=1;column<=n;++column) 
{ 
    if(place(row,column)) 
    { 
    board[row]=column; //no conflicts so place queen 
    if(row==n) //dead end 
    print(n); //printing the board configuration 
    else //try queen with next position 
    queen(row+1,n); 
    } 
} 
}

是的，這是回溯。因爲它會嘗試每個可能的解決方案候選人，直到完成一些條件。在某些row值上，for(column=1;column<=n;++column)將確保嘗試每個可能的值column並檢查它是否可行與place(row,column)，然後更深入row +1。完成此操作後，此算法將恢復到下一列。

換句話說，該算法將打印所有可能的解決方案，即n -queen。

來源

2015-11-24 07:19:36 ibrohimislam

接受，由於你對*「這個算法會打印**每個**可能的解決方案**」的洞察力* –

回溯隱藏在函數queen()的遞歸調用中。它通過嘗試和錯誤檢查列的列，如果發現命中，則放置後者。然後遞歸地調用函數queen()與下一行並遍歷列的下一行列，直到找到皇后不能被打敗的地方。重複這個遞歸調用直到所有的皇后被放置。

回溯的主要思想是嘗試和錯誤的方法。如果不是所有的皇后都可以放置，算法會跳回一個樹枝並從下一列開始。

來源

2015-11-24 07:30:20 gmug

這就是我最初的想法，但是如果一切順利，行/女王1，2，3和皇后4失敗，到達循環的結尾？直觀地說，這可能表明女王3或者甚至2或者1被「過早地」放置，並且需要嘗試不同的位置。在這個代碼中我沒有看到重新定位女王1的能力，例如，*成功定位後*。思考？ –

啊，好的。我現在看到它。在@ ibrohimislam的答案中，我們知道'if（row == n ）print（n）;'是解決方案的一個不可或缺的部分。 –

回溯是由queens函數結束處的implucit return聲明完成的。它在所有列被檢查後出現，即您提到的詳盡搜索。

要更清楚地看到它，請重寫函數以使用顯式堆棧數據結構來代替隱式調用堆棧。那麼回溯將被明確表示爲pop(stack)。

來源

2015-11-24 08:15:36

N皇后拼圖 - 這個解決方案中的回溯在哪裏？

回答

相關問題