"Кубик Рубика"

ЧИСЛО БОГА
В разделе "сборка прямым перебором" осуществляется сборка кубика прямым перебором с последовательным переходом от уровня к уровню. Т.е., сначала пытаемся собрать за один ход, потом - за два и т.д. до бесконечности :), которая, как не трудно догадаться, наступает очень быстро.
1 уровень - 12 ходов, в сумме всего 12 (каждая из 6 граней по две степени свободы на один ход)
2 уровень - 12*12+12 = 156 ходов, в сумме всего 12*12+12*2 = 168 хода
3 уровень - 12*12*12+12*12+12 = 1884 хода, в сумме всего 168*12+12*3 = 2052 хода

tab

Чтобы никого не мучить, переходим к 20 уровню, на котором, по словам "проверивших все на суперкомпьютере, собирается любой кубик... 20 уровень- в сумме всего 4 562 491 230 681 292 707 360 ходов, что вы можете проверить самостоятельно по формулам:

кол-во ходов на уровне n это сумма геометрической прогрессии = 12(12**n - 1)/11
а "в сумме всего ходов" для n уровня = (12**(n+1)-12-11*n)*12/121
т.о."сумма всего ходов" от уровня n-1 к уровню n растет как *12+12*n
ну а всего ходов на уровне от уровня n-1 к уровню n растет как *12+12

При текущей скорости 100 ходов в секунду на i5 (3ГГц), окончания двадцатого уровня придется ждать 1 446 756 478 526 лет, а наиболее реальным представляется срок в 23 года - 10 уровень, 11 - уже 280 лет.
Сразу же хочу огорчить оптимистов "на суперкомпьютерах" которые советуют переписать код на assembler, т.к. простой расчет показывает: если даже в один такт процессора вложить один ход с проверкой на собранность, что маловероятно, скорее надо спец. процессор с соответствующей архитектурой изготавливать, то получается, что на 3 ГГц перебора двадцатью ходами все равно придется ждать 144 675 с половиной лет.
Остается надеяться на спецпроцессор в 100 ТГц, который позволит получать один результат уже за 1,5 года.
Вот тогда "суперкомпьютеры" и позволят, видимо, что-то там показать или доказать. А пока можно довольствоваться лишь теоретическими выкладками и наслаждаться крутящимся в бесконечности кубиком. Число всех достижимых различных состояний кубика Рубика 3x3x3 равно
(8! * 3**(8-1)) * (12! * 2**(12-1))/2 = 43 252 003 274 489 856 000.
Это число не учитывает то, что ориентация центральных квадратов может быть разной.
С учётом ориентации центральных квадратов количество состояний возрастает в 4**6/2 = 2048 раз,
а именно до 88 580 102 706 155 225 088 000 состояний.
Если вспомнить про 4 562 491 230 681 292 707 360 ходов прямого перебора двадцатью ходами и откинуть пусть два порядка "ненужных ходов", например, поворот вторым ходом той же грани, что в первом ходе, но в обратную сторону, или поворот одной грани три или четыре раза в одну сторону, т.е. откинуть все ходы, которые дают повторяющиеся варианты кубиков, то, как раз получится, что за 20 ходов можно получить все "возможные" кубики. Что не противоречит уже доказанному - "Число Бога" =20
Если отдать себе отчет в том, что откинуть два порядка - это все равно, что откинуть почти 100%, то становится ясно, что при прямом переборе двадцатью ходами процент отхода(повторяющиеся кубики) к двадцатому ходу должен будет составить почти сто процентов, а процент уникальных кубиков будет где-то в десятой доле одного процента.
Например, чтобы из 4562 всех комбинаций кубиков получить 43 уникальных комбинации (откинуть два порядка) придется вычесть 4519, где 4519 составляет от 4562 примерно 99,06 процента и, стало быть, процент уникальных комбинаций будет 100-99,06=0,94 девяносто четыре сотых процента.
возникает вопрос: а можем ли мы оценить процент возникновения уникальных, например, кубиков при прямом переборе в зависимости от количества ходов, т.е. в зависимости от полного количества получаемых кубиков?
Для ответа на этот вопрос пришлось провести некоторые измерения, в результате которых процент на уровне двадцати ходов был оценен как три десятых (0,327), что соответствует 14 926 809 654 738 127 223 (14 вместо 43) уникальным кубикам.
Ошибка составляет менее половины порядка! и это с учетом того, что для интерполяции на интервале 10**18 за опорный был взят промежуток от 0 до 10**6.
Привожу все экспериментальные данные в виде графиков для наглядности.(файлы с табличными данными для желающих могут быть скачаны с этого сайта) На рисунке 1.2. представлены графики роста количества кубиков в зависимости от ходов перебора.
ris12

Ясно, что ВСЕ кубики растут строго по диагонали, по определению: один ход (поворот грани) - новый кубик. График повторяющихся кубиков растет быстрее графика уникальных. Так и должно быть, чтобы, в конце концов, к 20 уровню, мы получили свою десятую процента... На рисунке 1.1. представлены графики отношений повторов ко всем кубикам, уникальных ко всем и уникальных к повторам.
ris11

Здесь хорошо видна тенденция происходящего и хорошо видно как график отношения уникальных ко всем стремится к заветным десятым процента в перспективе. Перед тем как перейти к его степенной экстраполяции еще пару слов о побочных результатах. (Кстати желтый график имеет тенденцию к пересечению лилового, что, видимо, обусловлено маленьким начальным промежутком. Понятно, что отношение уникальных ко всем будет всегда меньше, чем - уникальных к повторам, т.к., повторы - это лишь часть от всех) Было интересно посмотреть, как именно повторяются кубики: сколько раз повторяется каждый, с какой частотой и т.д. На рисунке 2.3. видно сколько раз повторялись кубики в пределах 10000 уникальных экземпляров.
ris23

В принципе понятно, что, чем позже появился уникальный кубик, тем меньшее количество раз он успел повториться. Что и подтверждается этим графиком. Интересны исключения из правила. Первый из уникальных повторился 1395 раз, в то время как четырнадцатый уникальный повторился 3084 раза. это видно на рисунке 2.1.
ris21

График количества повторов отнюдь не плавный, м.б. он стал бы таким, будь промежуток измерения побольше. Это хорошо видно на рисунке 2.2. (промежуток с 2000 по 2200 уникальный кубик)
ris22

Серийность появления уникальных и повторяющихся кубиков занимательна тем, что абсолютно не похожа одна на другую. Понятно, что серия уникальных кубиков всегда сменяется серией повторяющихся, т.к. других кубиков нет по определению. Первый кубик, ясное дело, будет уникальным. Поэтому все нечетные серии - это серии уникальных кубиков. Все серии повторяющихся кубиков будут четными. Вторая, четвертая и т.д. На рисунке 3.1. и 3.2. хорошо видно, как неравномерно выглядят серии повторов: серии в один-два кубика сменяются выбросами в несколько тысяч повторяющихся кубиков.
ris31

(проанализировано было сто пятьдесят тысяч кубиков, которые разделились на двадцать пять тысяч серий)
ris32

Полную противоположность представляет из себя график прихода серий уникальных кубиков. На рисунке 3.4. видно, что серии приходят с определенной периодичностью и определенной конфигурацией самого периода.
Чтобы послушать "МУЗЫКУ СФЕР", задержите мышку на графике. (Разумеется, браузер должен уметь играть фоновый звук. IE, например)
Все в перделах одной актавы, в качестве величин задержек используются длины соответствующих четных серий (рис. 3.2).
ris34

Из графика 3.3. видна вообще потрясающая вещь: величина серии уникальных кубиков строго заключена в диапазоне от одного до десяти кубиков!
ris33

Это же видно и на рисунке 3.5. прирост "уникальных кубиков" от серий почти идеально линеен, от "повторов" - ступенчатый, что дает ступенчатость и суммарного графика
ris35

Настало время вернуться к аппроксимации графиков из рисунка 1.1. т.е. к обещанной оценке количества повторов при полном переборе, или количества уникальных комбинаций при полном переборе, что по большому счету одно и то же, если общее количество комбинаций при полном переборе нам строго известно и легко вычисляется по формуле (см.выше)
ris111

Лучший результат дала степенная экстраполяция. Формулы функций и погрешность можно видеть на рисунке 1.1.1.
14 926 809 654 738 127 223 - таким получается число уникальный кубиков за 20 ходов полного перебора.
Это число является числом одного порядка!!! с числом 43 252 003 274 489 856 000 - числом всех возможных вариантов положений кубика Рубика.
Кроме того, по результатам эксперимента можно построить следующую таблицу

tab1

Из нее, например, ввидно, что за шесть всевозможных ходов можно получить точно 989 247 разных кубиков, причем 883 294 из них даст именно шестой ход.
Или 989 247 разных кубиков из 43 252 003 274 489 856 000 возможных, могут быть собранными за шесть ходов, причем, 883 294 - последним шестым ходом, а 105 953, соответственно, соберутся на более раннем ходе...
Лиловым цветом в таблице как раз обозначены реально полученные данные по уникальным кубикам на уровнях перебора
ris41

Экстраполируя экспоненциальной функцией, хорошо видим, что к двадцатому уровню количество уникальных кубиков практически будет равняться общему количеству возможных состояний кубика Рубика. То есть, к двадцатому ходу соберется любой кубик. Другими словами, кубик Рубика 3х3х3 нельзя разобрать глубже, чем на двадцать ходов.
Сравните 37 833 872 816 882 300 000 и 43 252 003 274 489 856 000.
Эта оценка еще ближе к искомому результату чем первая!
Т.о. наша оценка говорит о том, что 21 ход - верхняя граница для сборки кубика Рубика 3х3х3 уж во всяком случае, а скорее всего, достаточно 20 ходов.
Кстати, в этом случае в разделе "оптимизация строки" в конечном итоге должно оставаться не более двадцати ходов... По большому счету все вышеизложенное не более чем шутка, мы судили о километровом отрезке графика по одному его миллиметру.
Другое дело, что в каждой шутке есть доля шутки. В любом случае нам никто не мешает перейти к изучению сборки "броском в двадцать ходов". предлагается изучить те же графики, что и для сборки "прямым перебором". А заодно посмотреть динамику сборки "случайным образом".
Те же ученые из одного американского института говорят, что основное количество кубиков собирается пятнадцатью, шестнадцатью ходами. А к двадцатому ходу собираются лишь жалкие остатки в стотысячные доли процента. Если это так, кстати, то это еще один камень в наш огород с миллиметровыми аппроксимациями... Итак:
Привожу графики прихода серий повторяющихся кубиков, серий уникальных кубиков по сериям; графики прихода повторяющихся и уникальных кубиков и их суммы, т.е. ВСЕХ по сериям; графики отношений уникальных ко всем, повторам ко всем, уникальных к повторам по сериям и их аппроксимации; график повторяющихся кубиков по кубикам. Все эти графики можно сравнить с аналогичными- для сборки прямым перебором
ris51

Необходимо заметить, что несмотря на то, что графики прихода «уникальных» и «повторов» как бы поменялись местами, если сравнивать со сборкой прямым перебором; т.е. в случае сборки «ЧБ» «уникальных» приходит больше на начальном этапе, чем «повторов» рис. 5.5, графики рисунка 5.6 демонстрируют завидную преемственность…
Явно видимые максимумы на графику 5.9, легко объясняются, если посмотреть номера повторяющихся кубиков, это… правильно номера кратные 21, 22, 23…, т.е. это те кубики, которые приходят в результате первого, второго, третьего..., поворота граней. Само собой разумеется, что на первом повороте кубики начинают повторяться практически с двенадцатой итерации, т.к. двенадцатью исчерпывается все возможные «уникальные» кубики, которые можно получить поворотом одной грани, и т.д. В остальном же график вполне себе напоминает график уже приведенный выше, т.е., чем раньше пришел кубик, тем большее количество раз он успевает повториться.
Кстати, если снять измерения и построить графики ОТДЕЛЬНО для произвольного хода в «ЧБ», т.е. для каждого уровня-хода с первого до двадцатого, то выйдет, что графики рис.5.1-5.6 явятся их суперпозицией. В среднем все они будут выглядеть как на рис. 6.1-6.6 – графики для пятнадцатого уровня сборки, т.е. вполне будут походить на саму суперпозицию.
ris66

кроме того заметим, что все поуровневые графики, назовем их гармониками, похожи между собой, т.е. имеют схожий вид. Для нас это очень важно, т.к., если «дождаться» окончания графика двадцатой или даже пятнадцатой гармонии мы не можем в силу временных ограничений, то увидеть весь ход графика или его большую часть мы можем для четвертой или пятой гармоники, например. И, т.о., мы получим, наконец, представление о том большом промежутке графика, который мы экстраполировали в начале по его бесконечно малой части.
ris91

Графики двадцатой гармоники в своем начале имеют почти форму графиков случайной сборки (см. ниже), и, теме не менее, все же, видимо, повторят графики низших гармоник, т.к., думать иначе нет никаких предпосылок… Опять же характер функций графиков х.6 гармоник удивительно стабилен.
ris71

На последок приведем графики для сборки «случайным образом». Как т следовало ожидать на начальном этапе случайная сборка дает наибольшее количество уникальных кубиков, т.е. не смотря на все безнадежность кручения подряд всех граней случайным образом, эффект появления уникальных кубиков максимальный. За два миллиона поворотов граней ни один кубик не повторился более четырех раз.
ris109

На остальных графиках хорошо виден классический белый шум, как и ожидалось. Вообще сборку прямым перебором можно сравнить с заполнением воронки песком с самого низа послойно. Сборку «ЧБ» - с песчаными ниточками от низа до верха. А случайную сборку – с отдельными песчинками равномерно распределяемыми по всему объему заполняемой воронки. Все-таки треугольной воронки, а не ромбовидного сосуда, потому что большинство кубиков, как у нас вышло соберется не на пятнадцатом ходу а на двадцатом, или, во всяком случае – девятнадцатом.
ris101