Динамическое построение дерева с рекурсивным возвратом

Question

У меня есть проблема, которая мне нужна, чтобы решить проблему рекурсивного возврата.Это похоже на проблему n-queen, но отличается тем, что использует разные кандидаты с асимметричной доской.Всего существует четыре разных кандидата, каждый из которых зависит от одного и другого.У меня 2 туза, 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 .

Теперь моя проблема в том, что я хочу использовать дерево, чтобы отслеживать кандидатов в качестве родителей и потомков дерева.Я еще не реализовал дерево, но мне было интересно, является ли метод, показанный в этом примере, хорошим способом создания дерева.И если это хороший способ создать дерево, как начать, как дерево узнает, к какому родительскому элементу оно должно относиться к ребенку, а также вернуться назад, когда решение не подходит?

Iнадеюсь, я добавил достаточно информации об этой ситуации, заранее спасибо.

Answer 1

Я могу ошибаться, но, похоже, вы не совсем поняли, как алгоритм рекурсивного поиска должен работать в этом случае. Древовидная структура, которую вы хотите построить, обычно не реализована явно, а представляет собой структуру рекурсивных вызовов, которая будет выглядеть как дерево поиска. Если вы посмотрите на реализацию псевдокода здесь http://en.wikipedia.org/wiki/Backtracking, вы увидите, что древовидная структура не задействована, и возврат (выполненный, когда reject возвращает true) выполняется просто путем возврата из текущего вызова.

В вашем случае вы, возможно, захотите выполнить поиск по одной структуре данных, вместо того, чтобы копировать ее, поэтому возвращение означает, что вы удалили только что отобранный фрагмент, а затем вернули его.