Описание тега backtracking
Отслеживание с возвратом - это общий алгоритм поиска решений некоторой вычислительной проблемы, который постепенно создает кандидатов для решений.
Поиск с возвратом - важный инструмент для решения проблем удовлетворения ограничений, таких как кроссворды, словесная арифметика, судоку и многие другие головоломки. Часто это наиболее удобный (если не самый эффективный) метод анализа, для задачи о рюкзаке и других задач комбинаторной оптимизации. Это также основа так называемых языков логического программирования, таких как Icon, Planner и Prolog. Отслеживание с возвратом также используется в механизме различий (diff) для программного обеспечения MediaWiki.