Знайдено число Бога (для Кубика)

Знайдено число Бога (для Кубика)

Знайдено число Бога (для Кубика)

Я жодного разу не збирав Кубик Рубика. Навіть у дитинстві в мене завжди було багато більш цікавих справ. Але якщо чесно — у мене просто не виходило.

— Ерно Рубік, архітектор, творець Кубика Рубика

Минулого тижня відбулася подія, яка змусила мене дізнатися, що таке Алгоритм Бога, Число Бога, і як це пов’язано з кубиками.

Три на три на три — не так вже й складно

Комбінаторика — це такий розділ математики, в якому все можна по-різному перемішати. Цей безлад всім подобається, але любиш кататися, люби і саночки возити. В комбінаториці всі ці перемішування прийнято підраховувати.

Це не так вже й просто, майже як збирати Кубик Рубика.

Припустимо, ви знайшли три різнокольорових кубика Лего в кафе, де ви чекаєте когось, але цей хтось спізнюється. Ви починаєте по-різному з’єднувати ці три кубика, створюючи всілякі комбінації з них. Вам звичайно все одно, ви думаєте тільки про час.

Але комбінаторика знає — ви можете зібрати 3! унікальних конфігурацій. 3! це не трійка, яка повинна вас здивувати, це факторіал трійки. 3! = 1 × 2 × 3 = 6. «Більше шести конфігурацій зібрати не вийде», — говорить комбінаторика, але нам все одно, час підтискає.

— 3! варіантів перестановок трьох кубиків і чоловічок А. Але хіба Лего може асоціюватися з кафе?

Так от, якщо б ви крутили в кафе Кубик Рубіка, справа була б трохи більше безнадійним. Коли ми крутимо Кубик Рубіка, комбінаторика говорить нам наступне:

Я хотів придумати, як би наочно пояснити, наскільки це багато. Як вам таке — якби всі жителі Землі дивилися на кожне стан по 1 секунді, то їм знадобилося б 211 років, щоб все переглянути *. Тобто, щоб додивитися до 2010, треба було починати з 1799 року (уявляєте, народився Пушкін **, і давай на Кубик дивитися). Але тоді населення Землі було менше, тому все одно не встигли б.

— Те, що може зайняти 211 человечеств на цілий рік, можна купити за 30 рублів. Мене це ніколи не перестане вражати.

Причому тут Бог

Алгоритм Бога — Це такий алгоритм, який вирішує Кубик Рубіка за мінімальне число ходів. Найцікавіше, що ніхто навіть не знає, чи існує цей алгоритм чи ні. Це, мабуть, єдине, що у них спільного з Богом.

Число Бога для Кубика Рубика — мінімальне число ходів за яке Алгоритм Бога гарантовано вирішить будь-яку конфігурацію Кубика. Тобто існують конфігурації, які Алгоритм Бога вирішує за 1 хід. Але не Сущетсвует таких, на які він витрачає більше ходів, ніж Число Бога.

— Версія кубика на неодімових магнітах, яку можуть використовувати сліпі, хворі на дальтонізм і дуже нетерплячі (її легко розібрати). Можливо, ніхто крім Бога так і не дізнається алгоритм Бога для Кубика Рубіка, але грати в нього можуть майже все. Автор ідеї та фотографії — Ендрю Кертіс.

Минулого тижня кілька дослідників заявили. що вони вирахували число Бога.

Число Бога для алгоритму Кубика Рубика — 20. Так, шкода, що не 42.

20 — це досить звичайне число, але в контексті Кубика Рубіка немає числа більш саркастичного і знущального. Справа в тому, що в кубик Рубіка 20 рухомих деталей. Зізнайтеся, засмучуються ви хоч раз хотіли розібрати Кубик, щоб потім правильно його зібрати і заспокоїтися?

У цей час число Бога сміялося над вами!

Адже деталей-то теж 20.

Занадто багато цифр для однієї статті

Існують такі конфігурації Кубика Рубіка, які вимагають 20 ходів для вирішення — це стало відомо ще в 1995 році. Все, що залишалося довести дослідникам — відсутність конфігурацій, що вимагають 21 або більше ходів для вирішення.

Що може бути простіше, залишилося тільки поперебірать комбінації. Ось як вони вирішили це зробити ***:

  1. Розбити вихідні 43 252 003 274 489 856 000 станів на 2217093120 підмножин
  2. Скоротити число підмножин до 55882296, бо одні виходять з інших поворотами або дзеркальними відображеннями Кубика
  3. Чи не шукати оптимальне рішення для кожного стану, задовольнятися будь-яким не довше 20 ходів
  4. Написати програму, яка вирішує одне підмножина за приблизно 20 секунд

Пункт 1) дуже важливий для того, щоб виконати пункт 2). Треба бути хитрим лисом, щоб скласти підмножини саме так, щоб їх потім скоротити.

Небажання шукати оптимальні шляхи в пункті 3) теж не каприз. Вони звичайно могли б робити це, але їм немає чого — вони просто хотіли перевірити, що Число Бога це 20, а не знайти все оптимальні шляхи для всіх конфігурацій.

Обробивши всі підмножини, вони не знайшли жодного стану, який вимагає 21 або більше ходів для вирішення. А значить довели — Число Бога для Кубика Рубика дорівнює 20.

Як перевірити, що ви все зрозуміли?

Знайти Число Бога не значить знайти Алгоритм Бога. Якщо ви розумієте це і згодні, то ви все зрозуміли. Інакше, можете спробувати перечитати визначення Алгоритму Бога і Числа Бога.

Як утерти хлопцям ніс?

Ви можете обставити їх, я не жартую. Для це вам треба придумати алгоритм, який в пункті 3) буде шукати тільки оптимальні ходи. Це і буде Алгоритмом Бога, а вам, ймовірно, будуть цілувати ноги.

Цікаві факти по темі

  • Конфігурації Кубика, які вимагають 20 ходів для вирішення, не так вже й часто зустрічаються (приблизно +0,0000000007% від загального числа конфігурацій).

Перша була виявлена ​​тільки через 15 років після появи Кубика на світло.

  • Комп’ютери вирішують Кубик Рубика швидше, ніж люди на них дивляться. Для перебору всіх варіантів знадобилося 35 ядро-років. Це означає, що одне ядро ​​одного комп’ютера, на якому проводилися обчислення, впоралося б з ними за 35 років. Скільки ядер було у них в розпорядженні, дослідники не повідомляють.
  • Комп’ютерні потужності для вирішення завдання надала компанія Google, в якій працює один з дослідників.

    Навіщо?

  • Іноді в кінці статей я ставлю запитання — чому? Але сьогодні інша історія, адже не зовсім зрозуміло, навіщо знати число Бога для Кубика Рубика. Якщо ви думаєте, що я зараз скажу: «Попалися!», — Пожартую жарт і ненароком розповім, яку велику користь принесе це відкриття, то ви помиляєтеся. Я не знаю навіщо.

    Але я знаю, що ми можемо винести для себе з усього цього.

    Насправді, ми давно вже це винесли це для себе — якщо розбити задачу на підзадачі, то її рішення помітно спрощується. Вся проблема в тому, щоб правильно розбити.

    А ще наступають нові часи для науки, коли деякі речі стає швидше перевірити, чим довести. Але про це я одного разу вже писав мигцем.

    Розділяй і володарюй!

    * — У великому числі однакові конфігурації Кубика, повернені і відбиті, враховуються як різні; а під населенням Землі розуміється 6500000000 чоловік, які не сплять, не їдять, а тільки витріщаються на кубики 24 години на добу

    ** — В 1799 році народився самий неоцінений мною письменник Олександр Сергійович Пушкін

    *** — Пункти «. »І« PROFIT »опущені через повагу до читача

    Сподобалася стаття? Поділися нею з друзями!