Теория алгоритма бога

В основу теории Алгоритма Бога было заложено утверждение, что собрать Кубик Рубика необходимо не более 20 ходов.

Еще десять лет назад было доказано, что наименьшее число ходов для сбора кубика 23.Однако сейчас число ходов сократилось до 20, благодаря компании Google, которая потратила 35 лет компьютерных вычислений, чтобы доказать, что алгоритм бога Кубика Рубика 3х3 существует. Именно так его окрестили ученые, работавшие над поиском формулы по сбору кубика за 20 ходов. Для создания универсального решения было придумано множество алгоритмов, каждый из которых решал свою задачу по сбору той или другой грани Кубика Рубика.

Один алгоритм вычислял оптимальное решение для сбора фронтальной поверхности. Другой — верхних и нижних граней. Формул для сбора Кубика Рубика существует множество, отличающихся друг от друга по количеству ходов и степени сложности. Среднестатистический любитель этой головоломки умеет собирать кубик за 40 и более ходов. Поэтому алгоритм, который решает задачу по сбору Кубика Рубика за наименьшее число ходов, назвали «Алгоритм Бога».

Спустя 15 лет после того, как Эрне Рубик создал свою головоломку любители кубика доказали, что 20 шагов достаточно, чтобы собрать любой, перемешанный произвольным образом, кубик.

Формула Бога для Кубика Рубика 3х3

Не смотря на то, что учеными было доказано, что любую позицию можно собрать за 20 ходов, универсальной формулы для сборки Кубика Рубика пока не придумали. Но была выведена обобщенная формула бога для Кубика Рубика 3х3 которая решает 95% всех вариантов сборки.

B2 D2 FI R2 F U2 R2 FI R2 U2 F R U L B D RI D L2 UI

Для удобства сборки головоломки лучше всего за основу брать светлую грань белую или желтую.

Расшифровка формулы Бога (Этапы сборки)

• Этап №1

  B2 (back) — поворот задней стороны кубика по часовой стрелке 2 раза
  

• Этап №2

  D2 (down) — поворот нижней стороны кубика по часовой стрелке 2 раза
  

• Этап №3

  FI(front) — поворот фронтальной (передней) части кубика против часовой стрелки 1 раз
  

• Этап №4

  R2 (right) — поворот правой стороны кубика по часовой стрелке 2 раза
  

• Этап №5

  F (front) — поворот фронтальной (передней) части кубика по часовой стрелке 1 раз
  

• Этап №6

  U2 (up) — поворот верхней стороны кубика по часовой стрелке 2 раза
  

• Этап №7

  R2 (right) — поворот правой стороны кубика по часовой стрелке 2 раза
  

• Этап №8

  FI (front) — поворот фронтальной (передней) части кубика против часовой стрелки 1 раз
  

• Этап №9

  R2 (right) — поворот правой стороны кубика по часовой стрелке 2 раза
  

• Этап №10

  U2 (up) — поворот верхней стороны кубика по часовой стрелке 2 раза
  

• Этап №11

  F (front) — поворот фронтальной (передней) части кубика по часовой стрелке 1 раз
  

• Этап №12

  R (right) — поворот правой стороны кубика по часовой стрелке 1 раз
  

• Этап №13

  U (up) — поворот верхней стороны кубика по часовой стрелке 1 раз
  

• Этап №14

  L (left) — поворот левой стороны кубика по часовой стрелке 1 раз
  

• Этап №15

  B (back) — поворот задней стороны кубика по часовой стрелке 1 раз
  

• Этап №16

  D (down) — поворот нижней стороны кубика по часовой стрелке 1 раз
  

• Этап №17

  RI (right) — поворот правой стороны кубика против часовой стрелки 1 раз
  

• Этап №18

  D (down) — поворот нижней стороны кубика по часовой стрелке 1 раз
  

• Этап №19

  L2 (left) — поворот левой стороны кубика по часовой стрелке 2 раза
  

• Этап №20

  UI (up) — поворот верхней стороны кубика против часовой стрелки 1 раз
  

ВАЖНО!!! В процессе сборки кубика нужно быть внимательным относительно вращения граней по часовой стрелки и против часовой стрелки. Многие во время сборки путают направления вращения и потом говорят, что алгоритм бога Кубика Рубика не работает.

Напоминаем что данный способ подходит только для 95% ситуаций. Поэтому если у вас не получается большое количество раз собрать Кубик Рубика, нужно еще раз хорошенько его перемешать и повторить сборку по формуле Бога.

Научно исследовательская работа на тему: Математика волшебного кубика.

МБОУ СОШ № 19 Им. Б. И. Северинова

Всероссийская научно-практическая конференция школьников, студентов, аспирантов и молодых ученых «Исследования молодых – регионами»

Тема: » Математика волшебного кубика «

Выполнил(а): Федосеев Юрий Сергеевич

8 «А» класс СОШ № 19

Научный Руководитель: Рыбакова Е.И –

учитель математики СОШ № 19

Уфа 2012

Введение:

Любопытство подтолкнуло меня на изучение «Математики волшебного кубика». Все началось вот с чего. Как-то раз, шагая по улице, я увидел, что ребята собирают тот самый «Волшебный кубик»- кубик Рубика. При этом они собирали его очень быстро, будто у них пальцы в узел завязывались. Придя домой, я заглянул в интернет, чтобы научиться сборке. Выучив за сутки необходимую теорию, я отправился по магазинам в поисках хорошего кубика. Купив кубик, сборку отработал за два дня.

Основная часть:

Когда я начал изучать теорию таинственного кубика, я обнаружил такую историю…

Лучшая головоломка ХХ века, придуманная 13 лет назад венгерским преподавателем дизайна Эрнё Рубиком, упорно сопротивляется попыткам разгадать все ее тайны. Сразу после изобретения кубика Рубика начался поиск самого короткого пути к ее решению. Первые разработанные алгоритмы требовали 200-300 ходов (поворотов граней) для того, чтобы вернуть кубик в исходное состояние. Постепенно длина алгоритмов (т. е. минимальное число ходов, гарантирующее решение) сокращалась. Это происходило за счет изменения последовательности сборки разных частей головоломки (улучшения стратегии) и применения более коротких операций для перестановки и правильной ориентации маленьких кубиков (улучшения тактики). Ставший самым популярным послойный алгоритм кубика Рубика осуществляет сборку не более чем за 108 ходов. Совершенствуя его, удается уменьшить это число до 86 ходов. Дальнейшие улучшения требуют резкого увеличения количества формул, которые необходимо держать в голове или на бумаге в процессе сборки. В период всеобщего увлечения кубиком (1981-1988 гг.) редакция ‹Кванта› получила не менее десятка объемистых разработок, авторы которых, проделав гигантскую работу по поиску новых операций, получили алгоритмы, позволяющие решать «головоломку века» в среднем за 50-60 ходов. Наиболее основательную работу проделал московский инженер А. Карасев, разработавший таблицы для сборки кубика из 5412 операций, разбитых на 22 группы по 246 формул в каждой группе! Одновременно с любителями решать головоломку, держа ее в руках, неприступный кубик штурмовали и программисты. Сначала успеха добились «менее безумные» из них — те, кто взялись за Малый кубик размером 2X2X2 кубичка. Задачу они решали с конца.

В дальнейшем этот алгоритм удалось несколько улучшить — сначала этого добился сам англичанин, а пару лет назад Х. Клоостерман из Голландии довел длину алгоритма до 42 ходов. Важно отметить, что эта граница обоснована строго (а не эмпирически), т. е. доказано, что из любого состояния кубика Рубика можно вернуться в правильное не более чем за 42 хода, причем данный рекордный алгоритм не может гарантировать лучшего результата. (Это не означает, что другой алгоритм не может оказаться короче.) Конечно, это доказательство существенно использует компьютер (как, например, и относительно недавнее решение знаменитой «проблемы четырех красок»): для каждого из этапов сборки был осуществлен полный перебор вариантов, число ходов, понадобившееся в худшем случае, и принимается за «длину» данного этапа. Совсем недавно нового достижения добился немецкий математик Герберт Коцемба. Он был среди тех «менее безумных», кто 10 лет назад победили Малый кубик, но затем примкнул к «самым самым» и, возможно, уже остался единственным, кто до наших дней продолжал штурм головоломки века. Теперь к нему пришел заслуженный успех. Он разработал алгоритм и написал программу, которая решает головоломку Рубина менее чем за 21 ход! Сразу скажем, что эта оценка длины, в отличие от предыдущей, эмпирическая: все состояния кубика, которые предлагались программе Коцембы, были упорядочены не более чем за 21 ход. В частности, программа нашла более короткие решения для многих задач на составление узоров на кубика (или пасьянсов), весьма популярных в «золотую эру» кубика. Нет никакой гарантии, однако, что состояний, требующих больше 21 поворота по программе Коцембы, не существует вовсе. Более того, такую гарантию мог бы дать только полный перебор вариантов для каждого этапа программы (их два), а он пока не под силу даже программе Коцембы и его более мощному, чем у предшественников, компьютеру.

Идея алгоритма Герберта Коцембы

Собственно говоря, то, что придумал Коцемба, не является «алгоритмом сборки кубика» в том смысле, как его обычно понимают в «кубологии». Обычные алгоритмы сборки представляют собой наборы правил, позволяющих для любого заданного состояния кубика поставить некую ближайшую цель и достичь ее, выполнив последовательность поворотов граней, предписываемую правилами в данной ситуации. Тем самым кубик переводится в новое состояние, более близкое к правильному (по крайней мере, с точки зрения данного алгоритма). Например, цель может состоять в том, чтобы найти неправильно стоящий угловой кубичек и переместить его в свой угол, не трогая остальные угловые кубички. И таких маленьких шажков приходится делать очень много. В алгоритме Коцембы ставится только одна промежуточная цель — кубик надо перевести в одно из состояний, которые так и названы — промежуточными. Они характеризуются тем, что любое промежуточное состояние можно получить из правильного (а значит, и наоборот — превратить его в правильное)‚ поворачивая четыре боковые грани только а 180°‚ а верхнюю и нижнюю- а произвольный угол (естественно, кратный 90°). Первая цель (задача первого этапа) алгоритма Коцембы — восстановить такую раскраску из хаотического исходного состояния. При этом, конечно, можно пользоваться любыми поворотами. На втором этапе применяются только повороты, перечисленные выше. Легко понять, что они автоматически сохраняют нашу вспомогательную раскраску. По существу, на втором этапе происходит только установка каждого кубичка на его место. А благодаря сохранению вспомогательной раскраски правильная ориентация кубичков на своих местах будет обеспечена автоматически. Таким образом, число промежуточных состояний равно числу допустимых перестановок кубичков (т. е. перестановок получаемых из правильной поворотам граней), при которых реберные кубички среднего слоя остаются в этом слое. Отметим, что метод Коцембы также восходит к алгоритму Тистлетуэйта. Однако в последнем используются не один, а три вложенных друг в друга класса промежуточных состояний, отвечающих поэтапному сужению набора разрешенных поворотов; второй из этих трех классов и составляют промежуточные состояния Коцембы. Понятно, что если вам нужно добраться из пункта А (исходное состояние) в пункт В (правильное состояние) и по дороге обязательно посетить пункт С (промежуточное состояние). то такой путь АСВ может оказаться длиннее прямого пути АВ, даже если его отрезки АС и СВ проходятся оптимально. А если еще и на пути из А в С надо завернуть в D, а из С в В — в дополнительное промежуточное состояние Е. то получится еще более длинный путь АВСЕВ. Зато каждый из отрезков этого пути уже настолько сокращается, что полный перебор случаев становится возможным. Так и появились рекордные результаты Тистлетузйта и Клоостермана.

Как работает программа Коцембы

Грубо говоря, Коцемба заставляет машину просматривать всевозможные цепочки поворотов, разрешенных на соответствующем этапе, и ловить момент, когда цель этого этапа будет достигнута. Однако при таком лобовом подходе объем просматриваемых вариантов был бы слишком велик. Так, первый ход можно сделать 6х3=18 способами (любую из шести граней можно повернуть на один из трех углов — 180°; +90°), на втором и каждом из следующих ходов число способов равно 15, так как нет смысла дважды подряд поворачивать одну грань. Таким образом, возникает «дерево вариантов», от каждой ветви которого отходят пять следующих ветвей. Из-за сращивания ветвей дерева вариантов число 18 можно еще увеличить. (В свое время промелькнуло сообщение о том, что доказано существование состояний, не решаемых быстрее, чем за 21 ход; впрочем, оно могло быть не вполне достоверным.) Как видим, результаты, показываемые программой Коцембы, близки к наилучшим. Сокращения перебора Герберт Коцемба добился с помощью специальной фильтрующей программы. Она хранит определенную информацию о всех цепочках из, скажем, не более чем 8 ходов, и позволяет отсеивать состояния, которые заведомо не упорядочиваются (в смысле 1-го или 2-го этапов алгоритма) такими цепочками. Начав «сборку а, компьютер настраивается выполнить первый этап за 10 ходов. Он порождает первые два хода и включает фильтр на 8 ходов; если возникшее состояние не отсеется, производится третий ход и включается фильтр на 7 ходов, и т. д. Если на каком-то шагу произойдет отсев, надо поменять предыдущий сделанный ход. Пока что для всех позиций, предлагавшихся программе, удавалось осуществить первый этап не более чем за 10, а второй — не более чем за 14 ходов.

Заключение:

И в заключение я хотел бы сказать, что математика применяется не только для вычисления разных формул и решения задач, но и для решения различных головоломок. Ведь именно математика помогла человеку найти секрет сборки «Волшебного кубика Рубика». 300 ходов человек сократил в 15 РАЗ и теперь кубик загадку можно собрать за 20 ходов. Вот он прогресс математики.

Так же я понял, что нельзя останавливаться на достигнутом мной результате . На данном моменте я выучил только послойную сборку и сейчас изучаю скоростную (по методу Джессики Фридрих). С помощью нее можно собирать кубик довольно быстро. Мировой рекорд сейчас составляет 5,66 секунд, и я хочу его побить!

Список литературы:

1. М. Мыльников Всем кубикам кубик // Юный техник. -1982. — № 7.
2. В. Дубровский, А. Калинин Новости кубологии // Квант. — 1992. — № 11. — С. 52-56.
3. К. Кноп «Кубик Рубика: штурм твердыни, и снова о кубике». Компьютера.
4. Membrana.Ru: «Рубик и его кубик: раскрутка, сказочное везение, возвращение»
5. Публикации из журналов «Наука и жизнь», «Квант», «Юный техник»: алгоритмы, пасьянсы на кубике, каталог вращений кубика.
6. Кубик Рубика и проблема Хигмана. Материалы 20-й летней конференции международного математического Турнира городов.