Алгоритм A* и кубик Рубика: реализация на языке Haskell
Двенадцатый конкурс по функциональному программированию в этом году и семнадцатый с момента запуска этого процесса выдался на удивление особенным. Впервые в истории конкурсов на него не было прислано ни одного решения. А казалось бы, задание проще простого — написать программу, которая для заданного состояния кубика Рубика находила бы (кратчайший) алгоритм его сбора.Злые языки предупреждали, что у рассматриваемой системы (размера 3х3х3) более 43 квантильонов состояний, и что никакой компьютер не справится с расчётом алгоритма при помощи простого перебора. Но ведь человек как-то решает задачу. Да, зачастую человек берёт и использует типовые шаги. Но вот я, к примеру, собираю кубик при помощи типовых комбинаций, но у меня на сборку кубика уходит минут пять, в то время как умельцы могут это сделать за 10 секунд. Что, неужели они знают алгоритм Бога? Сомневаюсь. Так что задача была вполне решаема. Но никто не решил.
Я сам написал для проверки своих идей программу для перебора при помощи алгоритма А* для кубика Рубика произвольного размера. Далее представлена эта программа.
Ознакомиться с описанием программы
