Математика кубика Рубіка

Той факт, що кожна грань куба складається з трьох шарів по три блоки, має велике значення. Число три, здається, має специфічний сенс, зреалізований у деяких дивних зв'язках між людиною і природою. Мати — Дитя — Батько. Небеса — Земля — Пекло. Створення — Збереження — Руйнування. Народження — Життя — Смерть.

Складений кубик Рубіка

Ерно Рубік

Розкладений кубик Рубіка

Математика кубика Рубіка — сукупність математичних методів для вивчення властивостей кубика Рубіка з абстрактно-математичної точки зору. Вивчає алгоритми складання кубика, оцінки алгоритмів його збірки та ін. Заснована на теорії графів, теорії груп, теорії обчислюваності, комбінаториці. Всі права на будь-який тривимірний відтворення, і навіть на будь-яке графічне або екранне уявлення цього об'єкта, залишаються за Ерно Рубіком і будуть актуальні аж до закінчення 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 років!

Як зібрати кубик Рубика

Етапи складання:

• хрест в першому шарі; [1] [Архівовано 24 квітня 2016 у Wayback Machine.]
• кути першого шару; [2] [Архівовано 27 квітня 2016 у Wayback Machine.]

Метод Джесіки Фрідріх

На даний момент одним з найпопулярніших методів швидкісної збірки є метод Джесіки Фрідріх. У цій збірці не потрібно запам'ятовувати велику кількість формул, головне зрозуміти принцип.

Етапи складання:

1. Збірка хреста на одній зі сторін.
2. Збірка першого шару одночасно з другим.
3. Орієнтація елементів верхнього шару.
4. Перестановка елементів верхнього шару
5. ребра середнього шару;[3]

Метод Валерія Морозова (інтуїтивний) Завдання цього методу — не давати готові формули для заучування, а показати принципи збірки. Схема збірки:

1. Зібрати 8 кутових елементів.
2. 4 реберних елементи в середньому шарі збираються в хрест на будь-якій із бічних граней.
3. 8 інших реберних елементів збираються в правильні пари.
4. 6 центрів встановлюються кожен на свою грань.

Метод для складання кубика 5 × 5, розрахований на початківців, які вміють як мінімум збирати 3 × 3!

• хрест в останньому шарі;[4]
• ребер останнього шару;
• розстановка кутів останнього шару;
• розворот кутів останнього шару..[5]
• збираємо кубик Рубика за 31 хід.[6]

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 і зіставити кожному з ходів $\{F,B,U,D,L,R\}$ елемент симетричної групи $S_{48}$.

Тоді група кубика Рубіка $G$ визначається як підгрупа $S_{48}$, породжувана шістьма поворотами граней:

$G=\langle F,B,U,D,L,R\rangle$

Порядок групи $G$ дорівнює: $|G|={\dfrac {8!\cdot 12!\cdot 3^{8}\cdot 2^{12}}{3\cdot 2\cdot 2}}=43\ 252\ 003\ 274\ 489\ 856\ 000=2^{27}\cdot 3^{14}\cdot 5^{3}\cdot 7^{2}\cdot 11$

Кожна з $4{,}32\cdot 10^{19}$ конфігурацій може бути вирішена не більше ніж за 20 ходів (якщо вважати за хід будь-який поворот грані).

Найбільший порядок елемента в $G$ дорівнює 1260. Наприклад, послідовність ходів $(R\ U^{2}\ D^{\prime }\ B\ D^{\prime })$ необхідно повторити 1260 разів, перш ніж кубик Рубік повернеться в початковий стан.

«Алгоритм Бога»

Алгоритм Тістлетуейта

Тістлетуейт використовував ряд підгруп довжини 4

$G=G_{0}\supseteq G_{1}\supseteq G_{2}\supseteq G_{3}\supseteq G_{4}=\{1\}$, де:

• $G_{0}=\langle L,R,F,B,U,D\rangle$

Ця група збігається з групою кубика Рубіка $G$. Її порядок дорівнює

${\dfrac {8!\cdot 3^{8}}{3}}\cdot {\dfrac {12!\cdot 2^{12}}{2}}\cdot {\dfrac {1}{2}}=43\ 252\ 003\ 274\ 489\ 856\ 000$

• $G_{1}=\langle L^{2},R^{2},F,B,U,D\rangle$

Ця підгрупа включає в себе всі конфігурації, які можуть бути вирішені без використання поворотів лівої чи правої граней на ± 90 °. Її порядок дорівнює

${\dfrac {8!\cdot 3^{8}}{3}}\cdot 12!\cdot {\dfrac {1}{2}}=21\ 119\ 142\ 223\ 872\ 000$

• $G_{2}=\langle L^{2},R^{2},F^{2},B^{2},U,D\rangle$

Ця підгрупа включає в себе всі конфігурації, які можуть бути вирішені без використання поворотів лівої чи правої граней на ± 90 °. Її порядок дорівнює

$8!\cdot (8!\cdot 4!)\cdot {\dfrac {1}{2}}=19\ 508\ 428\ 800$

• $G_{3}=\langle L^{2},R^{2},F^{2},B^{2},U^{2},D^{2}\rangle$

Ця підгрупа включає в себе всі конфігурації, які можуть бути вирішені з використанням лише поворотів на 180 ° (half-turns). Вона отримала назву «група квадратів» (squares group). Її порядок дорівнює

$(4!\cdot 4)\cdot {\dfrac {4!\cdot 4!\cdot 4!}{2}}\cdot 1=663\ 552$

• $G_{4}=\{1\}$

Ця підгрупа включає в себе єдину початкову конфігурацію. На першому етапі довільно задана конфігурація з групи $G$ приводиться до конфігурації, лежачої в підгрупі $G_{1}$. Мета другого етапу полягає в тому, щоб привести кубик до конфігурації, що розташоване в підгрупі $G_{2}$, не використовуючи поворотів лівої та правої граней на ± 90 °. На третьому етапі кубик Рубик приводиться до конфігурації, що належить групі $G_{3}$, при цьому повороти вертикальних граней на ± 90 ° заборонені. На заключному, четвертому етапі, кубик Рубик повністю збирається поворотами граней на 180 °.

Індекси підгруп $[G_{i}:G_{i+1}]$ при $i=0,1,2,3$ рівні відповідно 2048, 1082565, 29400 і 663552.

Для кожного з чотирьох сімейств правих суміжних класів $G_{i}/G_{i+1}$ будується таблиця пошуку $T_{i}$, розмір якої збігається з індексом підгрупи $G_{i+1}$ в групі $G_{i}$. Для кожного класу суміжності по підгрупі $G_{i}$, таблиця пошуку $T_{i}$ містить послідовність ходів, що переводить будь-яку конфігурацію з цього класу суміжності в конфігурацію, лежачу в самій підгрупі $G_{i}$.

Щоб зменшити кількість записів в таблицях пошуку, Тістлетуейт використовував спрощування попередніх ходів. Спочатку він отримав оцінку в 85 ходів. Протягом 1980 року, цю оцінку було знижено до 80 ходів, потім до 63 і 52. Студенти Тістлетуейта провели повний аналіз кожного з етапів. Максимальні значення в таблицях рівні 7, 10, 13 і 15 ходам FTM відповідно. Оскільки 7 + 10 + 13 + 15 = 45, кубик Рубік завжди може бути розв'язаний в 45 ходів FTM.

Алгоритм Корфа

Алгоритм Коцемби дозволяє швидко знаходити короткі, субоптимальні рішення. Тим не менш, може знадобитися значний час, щоб довести оптимальність знайденого рішення. Був необхідний спеціалізований алгоритм пошуку оптимальних рішень. 1997 року Річард Корф опублікував алгоритм, що дозволяв оптимально вирішувати довільні конфігурації кубика Рубіка. Десять обраних випадковим чином конфігурацій були вирішені не більше ніж в 18 ходів FTM.

Власне алгоритм Корфа працює таким чином. В першу чергу визначаються підзадачі, достатньо прості для того, щоб здійснити повний перебір. Були використані такі три підзадачі:

1. Стан головоломки визначається лише вісьмома кутовими кубиками, положення та орієнтації ребер ігноруються.
2. Стан головоломки визначається шістьма з 12 реберних кубиків, інші кубики ігноруються.
3. Стан головоломки визначається іншими шістьма реберними кубиками.

Кількість ходів, необхідне для вирішення кожного з цих підзадач, є нижньою оцінкою кількості ходів, необхідного для повного вирішення. Довільно задана конфігурація кубика Рубіка вирішується за допомогою алгоритму IDA*, що використовує цю оцінку як евристику. Вартості рішення підзадач зберігаються у вигляді баз даних з шаблонами.

Хоча цей алгоритм буде завжди знаходити оптимальні рішення, він не дозволяє безпосередньо визначити, як багато ходів може знадобитися в найгіршому випадку.