Той факт, що кожна грань куба складається з трьох шарів по три блоки, має велике значення. Число три, здається, має специфічний сенс, зреалізований у деяких дивних зв'язках між людиною і природою. Мати — Дитя — Батько. Небеса — Земля — Пекло. Створення — Збереження — Руйнування. Народження — Життя — Смерть.Ерно Рубік Математика кубика Рубіка — сукупність математичних методів для вивчення властивостей кубика Рубіка з абстрактно-математичної точки зору. Вивчає алгоритми складання кубика, оцінки алгоритмів його збірки та ін. Заснована на теорії графів, теорії груп, теорії обчислюваності, комбінаториці. Всі права на будь-який тривимірний відтворення, і навіть на будь-яке графічне або екранне уявлення цього об'єкта, залишаються за Ерно Рубіком і будуть актуальні аж до закінчення 70 років з дня смерті автора.
Існує багато алгоритмів, призначених для перекладу кубика Рубіка з довільної конфігурації в кінцеву конфігурацію (зібрану, всі грані одноколірні). У 2010 р. строго доведено, що для перекладу кубика Рубіка з довільної конфігурації в зібрану конфігурацію (часто цей процес називають «складанням» або «розв'язуванням») достатньо не більше ніж 20 поворотів граней (ходів). Це число є діаметром графу Келі групи кубика Рубіка. Алгоритм, який розв'язує головоломку за мінімально можливу кількість ходів, називають алгоритмом Бога.
Факти Сотні тисяч відео-роликів про головоломку на YouTube 43,252,003,274,489,856,000 можливих комбінацій, і тільки 1 правильний розв'язок. Понад 350 мільйонів кубиків Рубіка продано в усьому світі. Якщо скласти їх в 1 ряд, то смугу з кубиків Рубіка можна було б викласти з Північного Полюса до Південного Полюса. Винайдено професором архітектури та дизайну Ерно Рубіком в 1974 році в Будапешті як навчальний посібник по геометрії, і не експортувався з Угорщини до 1980 р. Перша назва, дана винахідником — «Магічний Кубик». Головоломка була перейменована в кубик Рубіка після презентації на найстарішій виставці іграшок у Нюрнберзі 1980 року і подальшим мільйонним замовленням для США. На піку популярності 1980 року, головоломку крутив кожен п'ятий житель землі! Довжина ребра оригінального кубика Рубіка — 57 мм. Це «золотий стандарт» іграшки, обчислений Ерно Рубіком і досі утримуваний брендом Rubik's. Перший Чемпіонат Світу з кубика Рубіка відбувся в Угорщині в 1982 р. і був виграний студентом з Лос-Анджелеса на ім'я Мін Тай (Minh Thai), що зібрав кубик Рубіка за 22,95 сек. Змагання проходять в кількох номінаціях: збірка однією рукою, ногами, з закритими очима і навіть під водою на одному диханні. Вважається, що найдовше збирав свій кубик Рубіка британець Грем Паркер, який отримав його в подарунок на своє 19-річчя і нарешті зібрав його вперше зовсім недавно, в 47-річному віці, тобто через 26 років!
Як зібрати кубик Рубика Етапи складання: хрест в першому шарі; кути першого шару; Метод Джесіки Фрідріх
На даний момент одним з найпопулярніших методів швидкісної збірки є метод Джесіки Фрідріх. У цій збірці не потрібно запам'ятовувати велику кількість формул, головне зрозуміти принцип.
Етапи складання:
Збірка хреста на одній зі сторін. Збірка першого шару одночасно з другим. Орієнтація елементів верхнього шару. Перестановка елементів верхнього шару ребра середнього шару;
Метод Валерія Морозова (інтуїтивний) Завдання цього методу — не давати готові формули для заучування, а показати принципи збірки. Схема збірки: Зібрати 8 кутових елементів. 4 реберних елементи в середньому шарі збираються в хрест на будь-якій із бічних граней. 8 інших реберних елементів збираються в правильні пари. 6 центрів встановлюються кожен на свою грань.
Метод для складання кубика 5 × 5, розрахований на початківців, які вміють як мінімум збирати 3 × 3! хрест в останньому шарі; ребер останнього шару; розстановка кутів останнього шару; розворот кутів останнього шару.. збираємо кубик Рубика за 31 хід.
20 кроків Будь-яку позицію кубика Рубіка можна розв'язати не більш ніж за 20 кроків. Кілька років тому доведено, що для кубика Рубіка є розв'язок за 23 ходи. Тепер це число скоротилося до 20. Щоб це зробити, знадобилося 35 років комп'ютерного часу, пожертвуваного Гуглом. Кожен блок розв'язку використовував свій алгоритм — послідовність кроків для досягнення потрібної конфігурації. Наприклад, один алгоритм призначався для розв'язання верхньої межі, а інший — для позиціювання середніх країв. Є безліч різних алгоритмів, що розрізняються за ступенем складності і кількості необхідних кроків, але ті, які може запам'ятати людина, зазвичай вимагають понад 40 кроків. Розумно вважати, що Бог може використовувати більш ефективний алгоритм, який розв'язує завдання за найліпше число кроків. Цей алгоритм відомий як «алгоритм Бога». Число кроків у гіршому випадку називають числом Бога. Зрештою, показано, що це число — 20. Після винайдення кубика Рубика п'ятнадцять років пішло на пошук позиції, яка напевно розв'язується за 20 кроків. За 15 років після цього ми доведемо, що 20 кроків достатньо для будь-якої позиції.
Історія числа бога
До 1980 року було встановлено, нижня межа — 18, а верхня — ймовірно, близько 80. У таблиці нижче зібрані всі результати. Як ми впоралися з 43 252 003 274 489 856 000 позиціями Кубика Рубіка? Ми поділили всі позиції на 2 217 093 120 множин — по 19 508 428 800 позицій в кожному. Ми зменшили кількість множин для розв'язання до 55 888 296 на основі симетрії й покриття множини. Ми не шукали оптимального розв'язку, а тільки розв'язок з довжиною 20 або менше кроків. Ми написали програму, що знаходить розв'язок для однієї множини за 20 секунд. Знадобилося 35 років комп'ютерного часу для пошуку розв'язків будь-яких змін у кожній із 55 888 296 множин.
Розподіл простору позицій: Ми розбили велику задачу на 2 217 093 120 менших підзадач: у кожну входило по 19 508 428 800 різних позицій. Одна така підзадача легко поміщається в пам'ять сучасного комп'ютера, і цей метод дозволив досить швидко отримати розв'язок.
Симетрія:
Якщо повертати Кубик Рубика вліво-вправо або вгору-вниз, то, по суті, нічого не зміниться: число кроків у розв'язку залишиться тим же самим. Замість того, щоб розв'язувати всі ці позиції, можна отримати розв'язок для однієї та поширити його на повернені позиції. Є 24 різних орієнтації в просторі й 2 дзеркальних положення Кубика для кожної позиції, що дозволяє зменшити число розв'язуваних позицій в 48 разів. Якщо використовувати аналогічні міркування і скористатися пошуком завдання «покриття множини», то число підзадач зменшується від 2 217 093 120 до 55 882 296.
Устаткування:
У нас була можливість розв'язати 55 882 296 підзадач на потужностях Гугла і виконати всі обчислення за кілька тижнів. Гугл не розкриває характеристики комп'ютерів, але було витрачено 1.1 мільярд секунд комп'ютерного часу (Intel Nehalem, four-core, 2.8GHz) на виконання розрахунків.
Найважча позиція:
Ми знали протягом 15 років, що є позиції, які вимагає 20 кроків, але ми довели, що ні для однієї позиції та не треба більше. Позиції з розв'язками в 20 кроків рідкісні, але їх цілком можна зустріти в реальності. Імовірність зустріти таку позицію варіюється від 10 ^ (- 9) до 10 ^ (- 8). Ми точно не знаємо точну кількість таких позицій. Таблиця дає оцінку числа позицій для кожної довжини розв'язку. Для довжин від 16 і більше, числа є зразковими. Наші дослідження підтвердили всі початкові дані до 14 рядки включно, а 15 рядок — новий результат. На 11 серпня ми виявили 12 мільйонів позицій з довжиною розв'язку 20. Ця позиція була найскладнішою для наших програм.
Група Кубика Рубіка Кубик Рубіка може розглядатися як приклад математичної групи.
Кожний з шести поворотів граней кубика Рубіка може розглядатися як елемент симетричної групи множини 48 етикеток кубика Рубіка, які не є центрами граней. Більш конкретно, можна помітити всі 48 етикеток числами від 1 до 48 і зіставити кожному з ходів елемент симетричної групи .
Тоді група кубика Рубіка визначається як підгрупа , породжувана шістьма поворотами граней:
Порядок групи дорівнює:
Кожну з конфігурацій можна розв'язати не більш ніж за 20 ходів (якщо вважати за хід будь-який поворот грані).
Найбільший порядок елемента в дорівнює 1260. Наприклад, послідовність ходів необхідно повторити 1260 разів, перш ніж кубик Рубік повернеться в початковий стан.
«Алгоритм Бога»
Алгоритм Тістлетуейта
Тістлетуейт використовував ряд підгруп довжини 4
, де:
Ця група збігається з групою кубика Рубіка . Її порядок дорівнює
Ця підгрупа включає всі конфігурації, які можна розв'язати без використання поворотів лівої чи правої граней на ± 90°. Її порядок дорівнює
Ця підгрупа включає всі конфігурації, які можна розв'язати без використання поворотів лівої чи правої граней на ± 90 °. Її порядок дорівнює
Ця підгрупа включає всі конфігурації, які можна розв'язати з використанням лише поворотів на 180° (half-turns). Вона отримала назву «група квадратів» (squares group). Її порядок дорівнює
Ця підгрупа включає в себе єдину початкову конфігурацію. На першому етапі довільно задана конфігурація з групи приводиться до конфігурації, лежачої в підгрупі . Мета другого етапу полягає в тому, щоб привести кубик до конфігурації, що розташоване в підгрупі , не використовуючи поворотів лівої та правої граней на ± 90 °. На третьому етапі кубик Рубик приводиться до конфігурації, що належить групі , при цьому повороти вертикальних граней на ± 90 ° заборонені. На заключному, четвертому етапі, кубик Рубик повністю збирається поворотами граней на 180 °.
Індекси підгруп при рівні відповідно 2048, 1082565, 29400 і 663552.
Для кожного з чотирьох сімейств правих суміжних класів будується таблиця пошуку , розмір якої збігається з індексом підгрупи в групі . Для кожного класу суміжності по підгрупі , таблиця пошуку містить послідовність ходів, що переводить будь-яку конфігурацію з цього класу суміжності в конфігурацію, лежачу в самій підгрупі .
Щоб зменшити кількість записів в таблицях пошуку, Тістлетуейт використовував спрощування попередніх ходів. Спочатку він отримав оцінку в 85 ходів. Протягом 1980 року, цю оцінку було знижено до 80 ходів, потім до 63 і 52. Студенти Тістлетуейта провели повний аналіз кожного з етапів. Максимальні значення в таблицях рівні 7, 10, 13 і 15 ходам FTM відповідно. Оскільки 7 + 10 + 13 + 15 = 45, кубик Рубік завжди може бути розв'язаний в 45 ходів FTM.
Алгоритм Корфа
Алгоритм Коцемби дозволяє швидко знаходити короткі, субоптимальні розв'язки. Тим не менш, може знадобитися значний час, щоб довести оптимальність знайденого розв'язку. Знадобився спеціалізований алгоритм пошуку оптимальних розв'язків. 1997 року Річард Корф опублікував алгоритм, що дозволяв оптимально розв'язувати довільні конфігурації кубика Рубіка. Десять вибраних випадково конфігурацій розв'язано не більш ніж в 18 ходів FTM.
Власне алгоритм Корфа працює так. В першу чергу визначаються підзадачі, достатньо прості для того, щоб здійснити повний перебір. Були використані такі три підзадачі: Стан головоломки визначається лише вісьмома кутовими кубиками, положення та орієнтації ребер ігноруються. Стан головоломки визначається шістьма з 12 реберних кубиків, інші кубики ігноруються. Стан головоломки визначається іншими шістьма реберними кубиками. Кількість ходів, необхідна для розв'язання кожної з цих підзадач, є нижньою оцінкою кількості ходів, необхідної для повного розв'язання. Довільно задана конфігурація кубика Рубіка розв'язується за допомогою алгоритму IDA*, що використовує цю оцінку як евристику. Вартості розв'язання підзадач зберігаються у вигляді баз даних з шаблонами.
Хоча цей алгоритм буде завжди знаходити оптимальні розв'язки, він не дозволяє безпосередньо визначити, як багато ходів може знадобитися в найгіршому випадку.
Примітки