Кубик рубика анализ

КУБИК «Рубика» (анализ)

Число граней : 6 (столько же цветов)
Размерность грани : 3 х 3
Число элементов = число граней * (3 х 3) = (6 х 3 х 3) = 54


Председательствующий:
– Собрание любителей Кубика Рубика считаю открытым. Сегодня у нас в гостях Мудman. Он будет в качестве ДОКЛАДЧИКА. Что? У вас сразу вопрос? Ну, пожалуйста… Передайте товарищу микрофон.



Вопрос к ДОКЛАДЧИКУ:
– Сколько возможных состояний у Кубика?



– Если считать математически, то число состояний равно факториалу от числа элементов, т.е. = Факториал(6 х 3 х 3) = (54)! = 2,3084369733924138047209274268303e+71

НО!

Это не верно. Потому что элементы Кубика неодинаковы. По углам стоят элементы с тремя поверхностями, а по бокам с двумя. И сразу понятно, что угловой элемент может стоять только по углам. А боковой только сбоку. А у центральных элементов вообще только одна поверхность! И они, хотя и крутятся вокруг оси, но не перемещаются вовсе. И ВСЕГДА НАХОДЯТСЯ в первоначальном соотношении друг к другу: они задают каркас из шести центральных элементов, а все остальные вращаются вокруг них. Конечно, Кубик можно повернуть целиком, и тогда на грани «Фронт» окажется элемент другого цвета. Но таких вариантов всего шесть. При этом всего лишь поменяется система координат, но взаимное расположение центральных элементов останется неизменным.

Поэтому считать число возможных вариантов надо иначе:
12 боковых элементов образуют своё множество, и каждый из них может быть расположен двумя способами (поскольку имеет две поверхности), 8 угловых – своё. И число вариантов для каждого элемента из этого множества будет равно ТРЁМ. А центральные сами по себе. Они неподвижны. У них нет степеней свободы. Поэтому их считать не нужно.

Получается:

M = (12)! * 2 + (8)! * 3, где M – число состояний Кубика Рубика.

M = 958, 124, 160

т.е.

958 миллионов

124 тысячи

160 – Но!!!

Не все состояния из этого множества возможно реализовать на практике. Кубик Рубика замкнутая система. И если вы сдвигаете один элемент, то двигаются и все элементы этой грани.

Я не знаю, как исключить из расчитанного математически множества состояний – невозможные. Кроме, как написать программу, которую научить собирать Кубик. Сгенерировать методом перебора всё математическое множество и записать в файл на диск. А потом попросить программу собрать КАЖДОЕ состояние из этого файла. Если сборка окончится удачно, то оставить такое состояние в Базе, а иначе удалить.



У меня вопрос :
– Какой размер на диске будет у такого файла состояний.



– Давайте считать. Если мы будем хранить текущее положение Кубика в массиве (6 х 3 х 3) и тип массива будет Целое (Integer), то каждый элемент будет занимать два байта. Итого получится :
N = 54 * 2 = 108 байт.

M – число записей в базе данных.
N – размер одной записи.

L = M * N
L – размер базы данных.
 
L = 958124160 * 108 = 103477409280 байт
Или 101052157,5 Килобайт,
или 98683,74755859375 Мб,
или 96,370847225189208984375 Гб.

Современные магнитные диски уже позволяют хранить такие объёмы данных. У меня на диске D: свободно 440 Гб, то есть в 4,565696 раза больше, чем требуется.

Другое дело, что старые языки программирования типа Бейсик не смогут работать с файлами такого размера. Они ограничены размером в 2 Гб. Значит, придётся разрезать базу данных на файлы. Я бы ограничил размер одного файла 1Гб и получил бы 96 файлов. С хвостиком в 97-м.

А потом бы начал вычёркивать из Базы нереализуемые состояния. Интересно, что бы у меня осталось в итоге? Насколько бы моя База «похудела».



Вопрос :
– А сколько времени потребуется на обработку такой Базы данных?



Ответ :
– Давайте посчитаем.

Возмём Кубик, перемешаем и будем собирать, и считать движения. Сколько у вас получилось? У меня на сборку верхнего слоя ушло 42 движения. На сборку среднего – 24 движения. Но это только потому, что один из боковых элементов уже стоял на месте. В противном случае было бы, как минимум, на 8 движений больше. Плюс движения на подводку к стандартному состоянию, из которого как раз и начинается стандартная операция. На сборку «жёлтого креста» ушло 12 движений. Опять же, только потому, что он был уже на половину готов. В противном случае, пришлось бы потратить вдвое больше. А если бы начальное расположение было неудачным, то пришлось бы потратить ещё 8 движений на стандартную операцию и несколько на подводку, чтобы начать её. Итого в пределе на сборку «жёлтого креста» уйдёт от 24 до 32 движений. На расстановку угловых эл. уходит по 8 движений на одну операцию. Таких операций надо выполнить от одной до трёх. Получается 24 движения. И на поворот в нужное положение угловых эл. уходит по 8 – 16 движений на каждый эл. В зависимости от его расположения. Плюс повороты «жёлтой» грани, чтобы подвести нужный угловой эл. на тот угол, на котором происходит вращение. Итого около 52 движений на поворот угловых эл.

Что у нас получается?

На сборку верхнего слоя у меня ушло – 42 движения.
На средний слой – от 8 * 4 до 8 * 8 (это если вам крупно не повезло и все четыре боковых эл. стоят на своих местах, и все НЕПРАВИЛЬНО!), т.е. от 32 до 64 движений.
И на нижний слой на крест от 24 до 32 + и на расстановку углов 24 и + 52 на их поворот. Сколько выходит в сумме?

42 + 64 + 32 + 24 + 52 = 214 движений на сборку Кубика Рубика.

За еденицу движения принят поворот грани на 90 градусов (в любом направлении).

Заметьте! Все числа в сумме ЧЁТНЫЕ!!! Именно потому, что Кубик замкнут, и перемещение одного эл. невозможно. Именно поэтому математический подсчёт числа состояний даёт НЕПРАВИЛЬНОЕ число.

Давайте возьмём за среднее значение – 200 движений? Легче будет считать. И от истины мы отклонимся не так уж и далеко.

Я написал программу-тест на Бейсике и прогнал на своём компьютере. У меня получилось 1 000 000 движений за 1,5 минуты.

Если такая скорость сохранится и в программе сбора кубика (в тест-программе движения выполнялись попорядку + был блок сравнения текущего состояния Кубика с Искомым), а я не понимаю почему она должна сильно измениться (разве что из-за чтения Базы данных), но если будет работать кэш диска, то этот параметр не должен загубить всю работу.

Итого на моём компьютере сборка Базы из 958 миллионов записей займёт:

958124160 * 200 / 1000000 = 191624,832 миллионов шт. поворотов

191624,832 * 1,5 минуты = 287437,248 минут = 4790,6208 часов

4790,6208 часов = 199,6092 суток непрерывной работы.

Понятно, что программа должна быть написана так, чтобы допускать приостановку работы на промежуточном этапе с сохранением всего сделанного и запоминанием своего состояния. Дабы при повторном запуске продолжить работу с этого места.

Тогда эти 200 суток растянутся по дням в году. И я думаю за год или чуть больше можно закончить обработку такой Базы данных.

Останутся только те записи, которые можно физически собрать на настоящем Кубике Рубика.

Насколько уменьшится База данных в размерах?

Этого я не могу сказать. Но думаю, что, как минимум, в половину. А может быть и больше.



Чтобы получить ответ на этот вопрос надо ставить вычислительный эксперимент.

Как иначе?



P.S.

Наверное, такую работу уже кто-нибудь проделал. Но мне об этом ничего не известно. Все заняты бестолковым «майнингом», надувающим через крипто-валюты инфляционные пузыри в мировой экономике. Лучше бы вы занялись «майнингом» Шахмат, по предложенной мною схеме в недавней записке «Вы представляете» и «Задача» от 26.04.2020. И крипто-валюта бы у вас была, и Шахматы бы развивались.

Но до вас же путёвые идеи не доходят…

Кстати. Программа-тест на Бейсике оттранслированная в EXE-файл в MS Quick-Basice 4.5 выполняется втрое быстрее, чем под Windows-7 на 64-х разрядах из макроса в Excel. Миллион движений EXE-файл под Windows 98 на том же железе выполнил мне за 27 секунд! Вот и думайте.





21:28:13 14.10.2022          2A29B49A8A00



Докладчик:
– Кстати, я модифицировал подпрограмму движений граней Кубика. Она увеличилась в размере. Зато стала работать быстрее. И теперь тот же миллион движений под DOS EXE-файл от Quick Basic v4.5 выполняется уже не за 27 секунд, как раньше, а всего за 17 секунд!



– А под Windows-7 64bit из макроса в Excel?



– Меньше минуты.



– Насколько меньше?



– На 7 секунд. То есть 53 секунды на 1 000 000 движений. Это ВТРОЕ медленнее, чем тот же Алгоритм под DOS. Если бы DOS умел видеть современные БОЛЬШИЕ диски, то для подобных задач он был бы идеальным решением. А Виндоус бы мы выкинули на свалку! Пусть всеми этими финтифлюшками дети балуются. И молоденькие барышни с домохозяйками.

Подождите. Меня спрашивают. Что вы хотели спросить? Говорите. Полохо слышно. Постойте. Вас плохо слышно! Передайте микрофон товарищу из последнего ряда. Говорите.



– Я хочу спросить. А какова ценность такой работы? Что даст расчёт числа реальных состояний Кубика Рубика и получение в виде файлов по 1Гб такой Базы данных? Поймите меня правильно. Я не из тех, кто отрицает чистую науку и творчество. Но, согласитесь, потратить год на вычисления! (И ещё неизвестно сколько на написание программы сборки Кубика). А получить в итоге? Лишь число M! – Колличество действительно возможных состояний Кубика Рубика. – Это как-то уж очень-очень… непродуктивно… Извините. Как вы считаете?



– Отвечаю. Я считаю на компьютере. (Шутка).

Вы задали хороший вопрос. Спасибо.

Ну, во-первых, у меня будет не только число M и База данных. У меня будет программа.



– А зачем она нужна? Если все и так умеют собирать Кубик по слоям упомянутым вами способом. Этот способ был опубликован в журнале «Наука и жизнь» ещё в 80-е годы прошлого столетия. И все так и собирают. Хотя и не знают ПОЧЕМУ? надо вращать именно так, и не знают «Имена тех героев-программистов», которые 40 лет назад нашли НА ТОЙ технике это решение! Вот если бы ваша программа умела что-то ещё… Чего человек делать не умеет. Тогда другое дело…



– Пожалуй, вы правы. И особой радости в такой работе нет. И результат мизерный.

Но!

Не всё сразу. Ведь можно подойти к вопросу с другой стороны.

Допустим, что мы не будем создавать базу из всех возможных состояний, вычисленных математически и составленных Алгоритмом простого перебора. А сделаем наоборот.

Давайте писать в БАЗУ только те состояния Кубика, которые «уникальны»? То есть, берём начальное состояние Кубика (собранное) в качестве первой записи нашей БАЗЫ и добавляем в эту запись группу ПОЛЕЗНЫХ параметров. – Например, запишем перед состоянием в качестве первого ПОЛЕЗНОГО параметра номер ШАГА, т.е. текущее число поворотов граней, сделанное от НАЧАЛА БАЗЫ, от исходного состояния. В начале это число, этот ШАГ, этот ПОЛЕЗНЫЙ параметр будет НОЛЬ.

А за массивом состояния в эту же запись, в эту же строку добавим ОЧЕНЬ ПОЛЕЗНУЮ табличку из восемнадцати возможных движений. – Граней у нас ШЕСТЬ? ШЕСТЬ. Число имеющих смысл поворотов одной грани ТРИ (по часовой на 90', против часовой на 90' и поворот на 180'). ШЕСТЬ умноженное на ТРИ = 18. То есть, каждая запись в БАЗЕ будет содержать РЕАЛЬНОЕ состояние Кубика, полученное на своём ШАГЕ от начального положения, и список всех возможных движений – ИСХОДОВ из этого состояния. А за каждым движением оставим пустое место, чтобы ВЫПОЛНИТЬ!!! это движение и вписать на это пустое место ССЫЛКУ на ту запись, на ту строчку в нашей БАЗЕ, куда нас это движение приведёт!

И у нас получится тогда уже не бесполезная, не бестолковая БАЗА данных из всех возможных состояний по Кубику Рубика, которая будет только дисковое пространство пожирать, да компьютерное время, да мозги программиста.

А реальное ПОЛНОЕ РЕШЕНИЕ Кубика Рубика!!!

Программа расчёта будет постоянно добавлять в конец БАЗЫ всё новые и новые уникальные состояния Кубика, и записывать номер ШАГА и пустую табличку из 18 возможных исходов из этого состояния. Конечно, перед тем, как делать такую запись, программа должна убедиться, что полученное на ШАГЕ «H» (Аш) состояние УНИКАЛЬНОЕ, что больше в БАЗЕ такого нет. А для этого программа должна сравнить все состояния из БАЗЫ с текущим, и если оно НЕ УНИКАЛЬНОЕ, а уже есть в БАЗЕ, тогда запись в конец БАЗЫ не добавлять, а просто записать номер этой записи в качестве ссылки в табличку для предыдущего ШАГА.

И так постепенно БАЗА вся заполнится не только РЕАЛЬНЫМИ состояниями Кубика Рубика, но и всеми ПЕРЕХОДАМИ от одного состояния к другому! В ней появятся ссылки, связи между строками.

Конечно, на заполнение такой БАЗЫ потребуется больше компьютерного времени. И больше дискового пространства. Но зато, имея такую БАЗУ, можно без особого труда найти ПУТЬ из ЛЮБОГО состояния Кубика Рубика в ЛЮБОЕ!!!

И при этом выбрать САМЫЙ КОРОТКИЙ ПУТЬ!

Для этого достаточно сделать несколько выборок из БАЗЫ. Надо выбрать те записи, которые содержат ССЫЛКИ на КОНЕЧНОЕ (искомое) состояние. И отсортировать эту выборку по ПОЛЕЗНОМУ параметру «ШАГ» – H (аш). И, естественно, надо брать ту запись, которая будет иметь наименьший ШАГ.

А в той записи есть своё состояние Кубика, и на ту запись тоже есть где-то в БАЗЕ свои многочисленные ссылки. И надо снова сделать тоже самое: выборку и сортировку. Взять минимум. И повторять так до тех пор, пока не доберёмся до ШАГА = 0, то есть до НАЧАЛЬНОГО состояния (собранного Кубика). И тогда у нас выстроится ряд движений, которые привели из собранного состояния в наше конечное.

Теперь достаточно будет выполнить эти движения в обратном порядке и Кубик будет собран.



– А если нужен путь не в НАЧАЛЬНОЕ состояние, а в другое конечное?



– Этот путь тоже находится тем же способом. Ведь начальное состояние равноправно ко всем остальным. Просто оно взято за начало отсчёта.



– Но ведь параметр ШАГ приведёт нас только в начальное состояние! А не в другое конечное.



– А из начального через ПОЛЕЗНЫЙ параметр ШАГ мы можем попасть в любое другое состояние.



– Это значит, что путь из одного состояния до другого всегда будет лежать через собранный Кубик и равен сумме ШАГОВ из каждого до начального? Но ведь они могут лежать в одном ШАГЕ друг от друга!



– Хороший вопрос. Я подумаю над ним. Возможно удасться найти короткий путь, если научиться пересчитывать ШАГ и переносить точку отсчёта из начального в одно из искомых состояний. Но я пока не могу сказать вам, как выполнить такой пересчёт. Я подумаю. Спасибо за вопрос. Первое, что приходит на ум, надо вычислить разницу ШАГА между двумя состояниями. И тогда НОЛЬ переместится в одно из этих состояний. А во всех выборках ШАГ тоже пересчитывать… Но это надо проверить. Надо пробовать. Ещё раз спасибо за хороший вопрос.

Ещё вопросы есть? Если нет, то я закончил. До свидания.





8:18:02 22.10.2022          27F4AB5D800





P.S.

Всё оказалось много сложнее и печальнее.

Программу в первом приближении я написал. Она поработала месяц. А потом я понял, что мне не хватит времени, чтобы достичь результата.

В чём затыка. Поясняю. Оказывается, если у вас два мужика (брюнет и рыжий) и три кепки (белая, синяя и красная), то число комбинаций в множестве «мужик в кепке» равно: два умножить на три. А не ПЛЮС, как я неверно поставил при расчёте предельного числа состояний Кубика Рубика.

Поэтому получается не :

M = (12)! * 2 + (8)! * 3, где M – число состояний Кубика Рубика.

M = 958, 124, 160

т.е.

958 миллионов

124 тысячи

160 – шт.

А

M = (12)! * 2 * (8)! * 3, где M – число состояний Кубика Рубика.

M = 115, 880, 067, 072, 000

Т.е.

115 триллионов,
880 миллиардов,
67 миллионов,
72 тысячи,
 0 шт.

А такое количество записей никуда не лезет. Хотя и понятно, что не все состояния из этого числа возможны. Поскольку Кубик Рубика подчиняется законам симметрии. Стоит собрать кубик изначально с дефектом, и вы никогда его не приведёте в правильное начальное состояние. И точно также замечено, если вы собираете Кубик Рубика с «вывертом», то совершенно симметричный «выверт» необходимым образом получается и с обратной стороны. Иначе собрать НЕ ВЫХОДИТ! Значит, всё это кошмарное количество состояний нужно ещё поделить на число НЕВЕРНО (не симметрично) собранных Кубиков Рубика.

Но как определить это число? Я не знаю.

А вообще-то, задача очень красивая!

Я мысленно представляю её так. Начальное (собранное) положение Кубика Рубика – это нулевая комната. А в ней 18 дверей. За каждой дверью (одно из 18 возможных движений граней = 6 граней * 3 движения) скрывается новая комната (новое состояние Кубика). И каждая комната будет иметь свой номер. А внутри каждой комнаты снова 18 дверей. 17 из них ведут к новым комнатам с новыми номерами (состояниям Кубика), а через одну из них мы вошли из предыдущей комнаты. Все двери (движения) связаны через комнаты (состояния) своим Лабиринтом (графом). И если бы удалось построить весь этот лабиринт, то можно было бы находить кратчайший Путь (минимальное число движений) из любой комнаты (состояния) в любую.

Я надеялся, что я сумею получить такое множество всех состояний Кубика Рубика. Но вот прошёл уже месяц работы моей программы. Она создала тучу файлов. Отыскала тысячи и тысячи состояний. Но забила мне пространство на жёстком диске. И главное! Размер кэша (рабочего файла) всё растёт и растёт. А именно в рабочем файле я держу нерешённые записи. То есть те записи, в которых не все 18 дверей пронумерованы. А как только в комнате все двери пронумерованы, так я эту запись вывожу из кэша в наружные файлы. Там у меня хранятся уже полностью решённые записи. И они тоже не в одном файле, поскольку этих файлов будет очень много, а разобраны по цветам элементов на первой грани. 36 папок первого уровня, 36 папок второго уровня внутри каждой. И внутри 1296 файлов. То есть общее число файлов в пределе 36 * 36 * 1296 = 6 ^ 8 (шесть в восьмой степени) = 1679616 шт.

Но в этом случае, когда вместо знака «ПЛЮС» ставится знак «УМНОЖИТЬ» в самом начале расчёта предельного числа состояний, получается, что это кошмарное число записей нужно разделить всего лишь на 1, 679, 616 = около двух миллионов (округлённо). Но ведь одна запись содержит 128 байт. 4 байта длинное (Лонг) сквозной номер записи, 4 байта длинное (Лонг) номер шага (количество движений из начального положения), 48 байт описание текущего состояния Кубика числами от 1 до 6 (исключены центры, поскольку они неподвижны), а дальше 18 длинных целых типа Лонг по 4 байта – номера дверей, тех записей куда эта дверь (движение) приводит.

Т.е. получается, что каждый файл должен содержать в пределе 68, 992, 000 записей. Умножаем на 128 байт. Получаем по 8,2Гб каждый. А общий размер всей базы данных становится равен в пределе: 8,2Гб * 1, 679, 616 шт. файлов = 13 тысяч 490 целых и 3 десятых Терабайта. Получается, что надо иметь 14 тысяч Терабайтных жёстких дисков. А у меня всего на всего один. Если бы я был уверен, что база состояний Кубика «похудеет» при фактическом расчёте в число раз кратное свойству симметричности Кубика! То есть из общего числа всех возможных состояний уйдут те, которые принадлежат неправильным Кубикам Рубика (собранным изначально с дефектом). Вот тогда можно продолжать.

Но и в этом случае рабочий файл с нерешёнными ссылками (дверями без номеров) будет расти в прогрессии по мере расчёта. Он уже занял 72Мб! А каждое увеличение рабочего файла приводит к необходимости сравнения нового состояния с каждой записью в нём. Чтобы принять решение: новое это состояние, или оно в базе уже есть? С решёнными записями программа умеет искать в нужном файле. А с нерешёнными? Всё лежит в одной куче! Выходит, что кэш тоже надо дробить по тому же принципу. Иначе время сравнения всё растёт и растёт. Раньше она добавляла в базу шустро новые записи, а теперь по 4 – 5 шт. в минуту. Ищёт ответ: уникально новое состояние или нет. И для получения этого ответа тратится уйма времени. Надо всё делать иначе.

Для этого надо переписать программу заново. И при этом использовать двойную арифметику. Поскольку такое кошмарное число записей НЕ ЛЕЗЕТ даже в длинное целое типа Лонг = 4 байта. А занимает уже 6 байт. А значит, надо создавать новый ТИП данных. А значит, и размер записи вырастет! Поскольку внутри записи хранятся ссылки на сквозные номера записей. Они тоже по 4 байта. А увеличение размера записи приведёт к большему расходу дискового пространства. А я уже даже подробностей не помню. Как я её писал? Убей меня, не помню! Это было до Нового Года.

И нет уверенности, что программа не забьёт мне своими данными весь винт. А тогда всё полетит к чёртовой бабушке и рухнет. Так НИЗЯ. Надо сначала рассчитать, а потом уже делать.

Вот такие увлекательные приключения в жизни у программиста.

Вот так. Ку!





14:39:45 06.03.2023          118CA89CA874