В моей жизни было две бескорыстной любви - Кубик Рубика и язык программирования С++. И постоянно было желание объединить их в одну - написать программу-модель Кубика. Время от времени это желание возникало снова. И ничего не получалось. Проходило несколько лет, и я снова возвращался к этой идее.
В конце концов, думал я, в мире полно математиков и программистов, и наверняка эту задачу давным-давно решили.
Недавно жизнь опять свела меня с Кубиком и каково же было мое удивление, когда я узнал, что оказывается решения до сих пор нет. Есть только попытки решить ее численными методами.
Как-то один «умник» рассказывал мне о том, что «Задача трех тел» решается при помощи численных методов. Если этими методами невозможно просчитать простую механическую игрушку, то говорить об их применении в области гравитации и вовсе бессмысленно.
Хочу привести несколько впечатляющих примеров применения «численных методов» на Кубике Рубика.
«После изобретения Кубика Рубика пятнадцать лет ушло на поиск позиции, которая наверняка решается за 20 шагов. Через 15 лет после этого мы докажем, что 20 шагов достаточно для любой позиции.»
«Любая позиция Кубика Рубика может быть решена не более, чем за 20 шагов.Несколько лет назад было доказано, что для Кубика Рубика есть решение за 23 хода. Теперь это число сократилось до 20. Чтобы это сделать, потребовалось 35 (тридцать пять) лет компьютерного времени, пожертвованного Гуглом.» (Там же).
«На 11 августа 2010 года мы обнаружили 12 миллионов позиций с длиной решения 20.» (Там же).
На сегодняшний день есть несколько довольно занятных программок, которые находят наиболее оптимальный вариант сборки Кубика из любой позиции. Одной из таких программ является Cube Explorer.
Однако все они используют алгоритмы «численных методов» и выбор из существующей базы состояний Кубика.
Желающие могут подробнее прочитать об этом в Википедии в статье «Математика кубика Рубика».
Итак, я уже говорил (http://wlad55wlad.livejournal.... о том, что к началу 21 века оказалось, что Человечество не имеет ФУНДАМЕНТАЛЬНЫХ знания вообще.
Оказывается, что вся «мощь» Человечества не позволяет решить даже такую простую задачу как ПОЛНОЕ описание Кубика Рубика.
«Полный же перебор всех вариантов состояний кубика Рубика сегодня не под силу не только персоналкам, но и мощным рабочим станциям. Даже если ограничиться только "легальными" состояниями, то есть теми, которые можно получить, не ломая механическую головоломку и не переклеивая на ней цветные наклейки, все равно число состояний кубика имеет тот же порядок, что и ответ в знаменитой древней задаче о награждении изобретателя шахматной игры. Помните эту историю? "На первую клетку, о господин, положи мне одно зернышко пшеницы, на вторую - два зернышка, и так далее, на каждую следующую клади вдвое больше, чем на предыдущую". При таких скромных запросах изобретателя на доске оказывается ни много ни мало, 264-1 зерен пшеницы - намного больше, чем может взрастить вся наша планета за один год.»
Сегодня я начинаю цикл заметок, в которых собираюсь для начала на понятийном уровне описать Кубик Рубика. И, по возможности, найти путь для создания его математической модели.
+
Оценили 2 человека
2 кармы