[Из песочницы] Алгоритм Х или что общего между деревянной головоломкой и танцующим Линком?
Предисловие
Как-то в гостях мне в руки попалась головоломка, в которой из 25 одинаковых фигурок требовалось собрать куб. Я провозился с ней почти весь вечер, и как можно догадаться, абсолютно безрезультатно. Тем не менее, я не мог сдаться просто так.
Не можешь сам — заставь компьютер. Сказано — сделано. В результате написанному по наитию алгоритму пришлось работать всю ночь, чтобы найти все 4 уникальных решения. В процессе гугления решений для сравнения, я нашёл программу Burr Tools, которая справилась с этой задачей за 3 минуты на моём ноутбуке.
Такая разница в скорости заставила меня разобраться, как решается эта задача и ещё целый класс подобных.Так как же решается эта задача и ещё целый класс подобных?
