Кодинг-приключение: собираем кубик Рубика с помощью алгоритмов
Разработчик решил не мучиться с кубиком вручную, а написать свой солвер — и это оказалось увлекательнее, чем ожидалось.
Если вы когда-нибудь пытались собрать кубик Рубика и сдались на середине, то этот материал для вас. Герой видео из серии "Coding Adventure" пошёл другим путём: вместо того чтобы учить схемы сборки, он написал программу, которая делает это за него. И, как водится, всё пошло не по плану.
Сначала автор попробовал простой BFS (поиск в ширину), но быстро понял, что для 43 квинтиллионов комбинаций это не вариант — даже суперкомпьютер бы задумался. Тогда он перешёл на более продвинутые алгоритмы, вроде IDA* с эвристикой, и тут началась магия. Программа стала находить решения за секунды, хотя иногда выдавала такие последовательности ходов, что руками их повторить было бы проблематично.
Особенно забавно было наблюдать, как солвер иногда "залипает" на локальных оптимумах — прямо как разработчик, который пытается понять, почему CI падает уже третий раз подряд. Но в итоге всё заработало, и кубик был собран. Автор даже добавил визуализацию, чтобы можно было посмотреть на каждый ход в 3D — для тех, кто хочет не только код, но и красивое представление.
Подход, кстати, универсален: те же алгоритмы можно применить к любым задачам поиска пути — от навигации роботов до оптимизации маршрутов доставки. Так что если ваш проект застрял на этапе "как это вообще решить", вспомните про IDA* и кубик Рубика. А если не поможет — просто напишите свой солвер, хуже не будет.
Комментарий студии METABYTE: Мы тоже любим решать сложные задачи, но обычно наши клиенты не просят собирать кубик — им нужен работающий продукт. Хотя, если понадобится, мы и кубик запрограммируем, и CI починим.