Рубрика «кубик рубика» - 4

Алгоритм A* и кубик Рубика: реализация на языке HaskellДвенадцатый конкурс по функциональному программированию в этом году и семнадцатый с момента запуска этого процесса выдался на удивление особенным. Впервые в истории конкурсов на него не было прислано ни одного решения. А казалось бы, задание проще простого — написать программу, которая для заданного состояния кубика Рубика находила бы (кратчайший) алгоритм его сбора.

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

Я сам написал для проверки своих идей программу для перебора при помощи алгоритма А* для кубика Рубика произвольного размера. Далее представлена эта программа.

Читать полностью »

Недавно я решил написать программу, которая будет выдавать алгоритм решения некоторых механических головоломок, таких как кубик 2х2х2, 3х3х1, пирамидка и других. Полный список есть в интерфейсе программы, а также на её сайте, но об этом позже. Естественно, алгоритм этот должен быть самым коротким, иначе не интересно: можно было бы забить туда известные формулы, чтобы она собирала как человек. Сразу скажу две причины, почему я не стал включать в список кубик Рубика 3х3: во-первых, из за его популярности. Наверняка есть уже куча софта для этого, не хочется изобретать велосипед. Ну и во-вторых, из за его сложности: начав писать программу, я хотел «потренироваться» на чём-нибудь попроще. Итак, приступим. Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js