Где применяется
1. Задача
Поставь 4 шахматных ферзя на доску 4×4 так, чтобы никакие два не били друг друга. Ферзь бьёт по своему ряду, своему столбцу и обеим диагоналям. Значит, никакие два ферзя не должны стоять на одной такой линии. Задача того же вида возникает в расписании экзаменов: два экзамена с общими студентами нельзя ставить в одно время. Или во встречах: две встречи с общим участником не должны пересекаться.
Можно перебрать все способы расставить фигуры и потом выбросить неправильные. На обычной доске 8×8 способов поставить 8 ферзей 4 426 165 368, а правильных среди них 92. Если проверять правило только в конце, когда все фигуры уже стоят, почти вся работа уйдёт на расстановки, которые испортились ещё на второй фигуре.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- сгенерировать все подмножества/перестановки/комбинации
- n маленькое (примерно n <= 12-20), экспоненциальный перебор допустим
- сделать выбор, уйти в рекурсию, затем отменить выбор перед следующим
- расставить элементы с ограничениями и откатиться при конфликте (N ферзей, судоку)
- вернуть все допустимые варианты, а не один
Похоже, но не то
- Рекурсия (Recursion)
Рекурсия спускается и возвращается. Бэктрекинг ещё и возвращает состояние назад при выходе.
- Рекурсия с мемоизацией (Recursion with memoization)
Кеш окупается, когда аргументы повторяются. На пути из разных выборов это бывает редко.
- Динамическое программирование (1-D) (Dynamic programming (1-D))
Динамика считает или оптимизирует, ничего не перечисляя. Бэктрекинг нужен, когда нужны сами варианты.
- Поиск слова в матрице (DFS/backtracking по сетке) (Matrix word search (grid DFS/backtracking))
Это тот же приём на сетке. Выбор там в том, в какого соседа шагнуть.
Ответ растёт экспоненциально, поэтому n маленькое. Подмножеств из 20 элементов 1e6, перестановок из 10 около 3.6e6.
На LeetCode
Задачи на расстановку, где фигуры не должны конфликтовать, например ферзи на доске или цифры в судоку. Держи множества занятых строк, столбцов и диагоналей, проверяй их за O(1) перед каждой постановкой и отменяй на обратном пути.
Только учётная половина урока, по множеству на строку, столбец и квадрат 3 на 3, без перебора.
Заполняй позиции по одной неиспользованными числами и обрывай ветку, как только правило делимости нарушено.
Ровно задача урока, с множествами диагоналей row минус col и row плюс col.
Пробуй цифры от 1 до 9 в каждой пустой клетке, проверяй множества строки, столбца и квадрата и отменяй, если дальше клетка застряла.