Вообще говоря, рекурсивный поиск с возвратом выглядит примерно так:
// On input, s represents a valid State up to depth d-1
sub do_it(int d, State s)
if (d == MAX_DEPTH+1)
// State s represents an answer! Print it and return.
else
(augment s to make it valid for depth d)
for each augmented_s
do_it(d+1, augmented_s)
end for
end if
end sub
// top level
do_it(0, empty_state)
Обратите внимание, что для данного s, действительного до глубины d-1, может быть несколько способов увеличить его досостояние действует до глубины d.Идея состоит в том, чтобы называть себя каждым из них.
Для этой проблемы «состоянием» является доска.Глубина «d-1» может означать, что первые столбцы d-1 заполнены.Юридически расширенными состояниями будут те, у которых в столбце d указана королева, так что ее невозможно захватить.
[update]
Вот еще один способ взглянуть на это.Решите проблему в обратном порядке.
Предположим, я прошу вас написать простую функцию с именем solver8().Эта функция принимает в качестве входных данных правление с ферзями, уже присутствующими в первых 7 столбцах .Все, что нужно сделать, это взять эту доску, найти все способы добавить королеву в восьмую колонку и распечатать эти доски.Как вы думаете, вы могли бы написать эту функцию?Хорошо;напишите это.
Теперь предположим, что я прошу вас написать почти простую функцию с именем solver7().Эта функция принимает в качестве входных данных правление с ферзями, уже присутствующими в первых 6 столбцах .Все, что нужно сделать, это взять эту доску, найти все способы добавить ферзь в 7-ю колонку и передать каждую из этих досок в качестве аргумента solver8().Не могли бы вы написать эту функцию?
Теперь предположим, что я прошу вас написать еще одну функцию с именем solver6().В качестве входных данных используется доска с ферзями в первых 5 столбцах.Все, что нужно сделать, это взять эту доску, найти все способы добавить королеву в 6-ю колонку, а затем передать каждую из этих досок на solver7().
И так далее, пока мы не доберемся до solver1().Эта доска занимает пустую доску, находит все способы разместить ферзю в первом столбце и передает каждую из этих досок solver2().
. Вы только что написали 8 функций, которые вместе решают проблему 8 ферзей.Если это не имеет смысла, запишите это как 8 функций и смотрите на них, пока вы не сделаете.
Теперь, если вы посмотрите на все эти функции, вы обнаружите, что они очень похожи.Поэтому вместо написания solver8, solver7, solver6, ..., solver1 вы пишете одну функцию:
solver(int n, Board b)
... такую, что solver (1, b) совпадает с solver1 (b), solver (2, b) такой же, как solver2 (b), ..., а solver (8, b) такой же, как solver8 (b).И вместо solver2 (...), вызывающего solver3 (...), например, у вас будет просто solver (2, ...), вызывающий solver (3, ...).Одна функция вместо 8, но делающая то же самое.
Вы довольно быстро обнаружите, что окончательный код чище, если вы начнете с solver9(), который просто берет заполненную доску и печатает ее, иsolver8() звоните.