На этом шаге мы кратко опишем реализацию такого перебора.
Перебор с возвратами (backtracking) - одна из самых важных парадигм разработки алгоритмов. Её можно считать "интеллектуальной" стратегией грубой силы (решением "в лоб"), выполняющей исчерпывающий поиск решений задач с заданными ограничениями и задач дискретной оптимизации. Подход может использоваться для решения огромного числа головоломок и задач, включая задачи о восьми ферзях, поиска пути в лабиринте, судоку, оптимизации рюкзака 0-1 и многие другие.
В самом общем случае методы перебора с возвратами сочетают в себе рекурсию и итерацию, имеют несколько параметров и обычно разрабатываются без строгого следования парадигмам декомпозиции и индукции. Поэтому тем, кто изучает материал впервые, они могут показаться сложными. К счастью, все алгоритмы перебора с возвратами зачастую имеют схожую структуру, что позволяет облегчить их разработку. Эта структура зафиксирована в так называемых "шаблонах перебора с возвратами", которые зависят только от языка и стиля программирования. Рассматриваемые далее методы обладают вполне определённой структурой с большим множеством параметров, что придаёт им достаточно большую степень свободы и лишь изредка требует дополнительных методов. При этом вы должны отдавать себе отчёт в том, что существуют и другие варианты их реализации. Но в любом случае можно относительно легко освоить перебор с возвратами, изучив приведённые в дальнейших шагах примеры и применив подобные алгоритмы к другим задачам.
На следующем шаге мы продолжим изучение этого вопроса.
