Кожна позиція кубика Рубіка може бути розв’язана за 20 або менше рухів.

Майже 35 CPU-років (прим. кого цікавить що це – читайте статтю, передостанній абзац) компьютерного часу було надано компанією Google, для того, щоб команда науковців змогла розв’язати всі можливі позиції кубика Рубіка, і зробити висновок, що не існує ситуацій, які б розв’язувались більше ніж за 20 рухів. Вважається, що будь-який оберт зовнішньої грані – це 1 рух (ця система також відома як “система напівобертів”).


Кожен, хто розв’язує кубик використовує певний метод, який складається з декількох етапів. На кожному етапі людина використовує алгоритми – послідовність рухів, яка призводить до того чи іншого результату, наприклад, до розв’язання верхньої грані. Потім використовує інші алгоритми, щоб розв’язати ребра середнього шару і т.д. Існує безліч різноманітних алгоритмів, що відрізняються за довжиною та складністю, і зазвичай людина у процесі розв’язку використовує більше 40 рухів.

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

З моменту, коли кубик Рубіка вперше з’явився на полицях в магазинах, пройшло близько 15 років, перш ніж знайшли першу позицію, яку неможливо вирішити менше ніж за 20 рухів. І як не дивно, ще через 15 років вчені змогли довести, що не існує позицій, які б розв’язувались більше ніж за 20 рухів.

Історія алгоритма Бога

В 1980 році нижньою межою була межа в 18 рухів, і саме вона лягла в основі аналізу числа Бога. Перша верхня межа була приблизно 80 рухів, беручи до уваги алгоритм, що був опублікований в одному з найперших буклетів. Таблиця нижче відображає всю історію пошуку числа Бога.

Дата Нижня межа Верхня межа Різниця Коментарі
Липень, 1981 18 52 34 Morwen Thistlethwaite довів, що достатньо 52 рухи.
Грудень, 1990 18 42 24 Hans Kloosterman покращив це число до 42 рухів.
Травень, 1992 18 39 21 Michael Reid показав, що 39 рухів достатньо в будь-якому випадку.
Травень, 1992 18 37 19 Dik Winter зменшив це число до 37 рухів лише через день!
Січень, 1995 18 29 11 Michael Reid зменшив верхню межу до 29 рухів проаналізувавши двофазний алгоритм іншого науковця – Herbert Kociemba (автора програми Cube Explorer).
Січень, 1995 20 29 9 Michael Reid довів, що позиція “суперфліп” (кути на місцях, ребра перевернуті на місці) потребує 20 рухів.
Грудень, 2005 20 28 8 Silviu Radu показав, що 28 рухів цілком достатньо.
Квітень, 2006 20 27 7 Silviu Radu покращив свою межу до 27 рухів.
Травень, 2007 20 26 6 Dan Kunkle та Gene Cooperman довели, що достатньо 26 рухів.
Березень, 2008 20 25 5 Tomas Rokicki зменшив верхню межу до 25 рухів.
Квітень, 2008 20 23 3 Tomas Rokicki та John Welborn наблизили верхню межу до 23 рухів.
Серпень, 2008 20 22 2 Tomas Rokicki та John Welborn продовжили зменшувати верхню межу і досягли 22 рухів.
Липень, 2010 20 20 0 Tomas Rokicki, Herbert Kociemba, Morley Davidson, та John Dethridge довели, що число Бога для кубика Рубіка – це 20!

Як це зробили?

Як розв’язали всі 43,252,003,274,489,856,000 позиції кубика Рубіка?

  • Розділили позиції на 2,217,093,120 набори по 19,508,428,800 позицій кожен
  • Зменшили кількість наборів, які необхідно розв’язати до 55,882,296 використовуючи симетрію та “set covering”
  • Не знайшли оптимального розв’язку для кожної позиції, але усі розв’язки були з довжиною 20 або менше
  • Написали програму, яка розв’язує один набор за 20 секунд
  • Використали 35 CPU-років щоб знайти розв’язки для всіх позицій в кожному з 55,882,296 наборів

Розділення

Одна велика задача була розбита на 2,217,093,120 маленьких задач, кожна з яких мала в собі 19,508,428,800 різних позицій. Кожна з цих маленьких задач була достатньою, щоб її можна було вирішити на звичайному сучасному комп’ютері, і саме такий шлях розділення (математично, використовуючи співмножини груп, що згенеровані рухами U, F2, R2, D, B2, L2, або просто – співмножинами Н) дозволив розв’язувати кожний набір досить швидко.

Симетрія

Якщо ви візьмете перемішаний кубик Рубіка, і перевернете його догори дригом, ви не зробите його складніше. Його розв’язок буде мати ту ж саму кількість рухів. Замість того, щоб вирішувати дві позиції, можна вирішити одну, а потім перевернути розв’язок для іншої. Існує 24 позиції, як можна зорієнтувати кубик Кубіка у просторі, а також віддзеркалювання позиції, що дозволяє досягти зменшення у 48 разів. Використовуючи аргументи простої симетрії і знайшовши розв’язок складної “set cover” задачі, вдалося досягти зменшення кількості наборів, які необхідно розв’язати з 2,217,093,120 до 55,882,296.

Достатні розв’язки проти оптимальних

Оптимальний розв’язок для позиції – це такий, який потребує найменшу кількість рухів для розв’язання. Відтоді як позиція, що потребує 20 рухів була знайдена, не потрібно було розв’язувати кожну позицію оптимально; достатньо було знайти розв’язок, що має 20 рухів або менше. Це значно полегшило справу; таблиця знизу показує швидкість сучасного персонального комп’ютера під час розв’язку випадкових позицій.

  Випадкові позиції Співмножини Н
Оптимально 0.36 2,000,000
20 рухів або менше 3,900 1,000,000,000

швидкість пошуку розв’язків, позицій в секунду

Програма для швидкого розв’язання співмножин

Оптимальна
кількість
рухів		 Кількість позицій
0 1
1 18
2 243
3 3,240
4 43,239
5 574,908
6 7,618,438
7 100,803,036
8 1,332,343,288
9 17,596,479,795
10 232,248,063,316
11 3,063,288,809,012
12 40,374,425,656,248
13 531,653,418,284,628
14 6,989,320,578,825,358
15 91,365,146,187,124,313
16 близько 1,100,000,000,000,000,000
17 близько 12,000,000,000,000,000,000
18 близько 29,000,000,000,000,000,000
19 близько 1,500,000,000,000,000,000
20 близько 300,000,000

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

Багацько комп’ютерів

Нарешті, можна було розподілити всі 55,882,296 співмножин Н серед багатьох комп’ютерів в Google та завершити розрахунки за кілька тижнів. Взагалі-то Google не розповсюджує інформацію про свої комп’ютерні системи, але для виконання цих розрахунків використовувались сучасні персональні комп’ютери (Intel Nehalem, чотирьохядерний, 2.8 GHz) з 1.1 млрд секунд, або 35 CPU-років.

Найскладніші позиції

Вже 15 років, як світ знає, що існує позиція яка потребує 20 рухів для розв’язання. Цим дослідом лише було доведено, що не існує інших, які потребують більшу кількість рухів.

Позиції в 20 рухів одночасно дуже рідкісні та дуже рясні. Вони трапляються рідше ніж в 1 млрд позицій, але таких позицій близько 300 мільйонів. Точна кількість їх невідома. В таблиці справа наведені усі можливі випадки в залежності від оптимального розв’язку. При кількості рухів 16 або більше, кількість позицій приблизна, і надана лише для порівняння.

Крім числа Бога, цей дослід підтвердив точну кількість позицій, що потребують від 0 до 14 рухів, а також вивів новий результат – точну кількість позицій, що потребують 15 рухів. Остання, до речі була підтверджена іншим незалежним дослідником.

На сьогоднішній день знадено близько 12 млн найскладніших позицій.

Автори

Група дослідників складається з Tomas Rokicki, програміста з Пало Альто, штат Каліфорнія, Herbert Kociemba, математика з Дармштадту, Німеччина, Morley Davidson, математика з Kent State University, та John Dethridge, інженера з Google в Mountain View.
Для зв’язку: rokicki@gmail.com або davidson@math.kent.edu.