動態樹建築與遞歸回溯

Question

我有這個問題，我需要解決遞歸回溯問題。它看起來很像n皇后問題，但它與使用不對稱板的不同候選者的方式不同。總共有四個不同的候選人，每個候選人都有依賴關係。我有2個ace，2個國王，2個女王和2個傑克。每個王牌必須與國王相鄰（水平或垂直），每個國王必須位於王后旁邊，而每位王后必須位於插孔旁邊，而非王牌位置必須在他們旁邊有重複。恰當的解決方案的主板看起來是這樣的：

Grid (y, x)(only the positions between *y,x* are available for candidates): 
4,1 4,2 *4,3* 4,4 
3,1 *3,2* *3,3* *3,4* 
*2,1* *2,2* *2,3* 2,4 
1,1 1,2 *1,3* 1,4 

Possible Solution 
. . K . 
Q J Q . 
. A K A 
. . J . 

現在我的問題是，我想用一棵樹來跟蹤考生家長和樹的孩子。我還沒有實現這個樹，但是我想知道這個例子中顯示的方法是否是創建樹的好方法。如果這是創建樹的好方法，我該如何開始，樹如何知道它應該在孩子身上哪個父母，並且在解決方案不適合時又回去？

我希望我已經增加了關於這種情況的足夠信息，在此先感謝。

Answer 1

我在這裏可能是錯的，但它不像你完全掌握了遞歸搜索算法在這種情況下應該如何工作。您想要構建的樹結構通常不會顯式實現，而是遞歸調用的結構，它看起來像搜索樹。如果您查看這裏的僞代碼實現http://en.wikipedia.org/wiki/Backtracking，您會看到沒有涉及樹形結構，並且僅在從當前調用返回時執行回溯（在拒絕返回true時完成）。

在你的情況下，你可能想要在單個數據結構上進行搜索，而不是複製它，所以回溯意味着刪除剛剛放下的候選件，然後返回。