Решатель куба Рубика для очень больших кубиков.
Решает любой куб любого размера от 1 до 65536. Код может быть легко изменен, чтобы обрабатывать еще большие кубики. Однако основным ограничением является объем памяти в системе и продолжительность времени, необходимое для решения. Решение времени растет ~ n^2, что означает, что в каждом измерении требуется в 4-5 раз больше, чтобы решить куб, который в 2 раза больше.
1024 слоистый куб может быть решена примерно за 1,5 секунды. Слоистый куб 16384 может быть решен примерно через 20 минут.
YouTube: решение 65536 слоев YouTube: Решение 32768 слоев
Изображение передней поверхности куба 32768
Решает центры, затем углы, затем края
Центры решаются на 15 этапах, где каждая стадия перемещает все части определенного цвета от одного лица на желаемое лицо. Например: сцена перемещает все зеленые кусочки на белом лице на зеленое лицо. Повторите это для всех цветов и лиц.
Решатель использует общение, описанное здесь, которое может переехать в центральные кусочки от одного квадранта лица до заканчиваемого на другое лицо. Очень важным свойством этого коммутатора является то, что можно изменить, чтобы одновременно перемещать много частей в одном ряду. Для очень больших кубиков это означает, что он может переместить сотни людей, если не тысячи кусочков за одну операцию. Среднее количество перемещений k = (2 * p + 5) / p, где p - количество элементов, которые можно перемещать в соответствии с операцией. К быстро приближается 2 по мере увеличения размера куба.
Углы решаются с использованием основного метода грубой силы перемещения углом на место, а затем вращаются до тех пор, пока лица не будут ориентированы правильно. Уилл Смит может объяснить: https://www.youtube.com/watch?v=wbzkdrc9vqs
Край решаются путем перемещения каждой пары краев на переднюю поверхность, а затем обменивая желаемые кусочки с левого края к правому краю. Ряд функций, где необходимо для исправления или предотвращения проблем с паритетом.
Вращения лица по сути бесплатны. Вместо того, чтобы перемещать все части на данном лице (n^2 частях), чтобы выполнить вращение, решатель просто изменяет систему координат, которая используется для чтения/записи на лицо. Это экономит огромный объем обмена данных.
// Virtually rotate this face by q * 90 degrees
inline void Face::RotatefaceCW ( const int q)
{
orientation = (orientation + q) & 3 ;
}
// Gets the value of this face at coordinates r = row, c = column
inline const byte Face::GetRC ( const uint r, const uint c) const
{
switch (orientation) {
case 0 :
return data[(r << BS) + c];
case 1 :
return data[(c << BS) + (R1 - r)];
case 2 :
return data[((R1 - r) << BS) + (R1 - c)];
case 3 :
return data[((R1 - c) << BS) + r];
default :
return 0 ;
}
}Этот код включает в себя простой экспортер изображений, который используется, рендеринг каждого лица в изображение.
https://www.nayuki.io/page/tiny-png-output
https://github.com/nayuki/nayuki-web-publised-code
Крошечный выход PNG - это небольшая автономная библиотека, доступная в C и C ++, которая берет RGB8.8.8 пикселей и записывает файл PNG.
Общее количество ходов может быть оценено с использованием простой формулы. Предполагая, что куб достаточно рандомизирован, мы можем ожидать, что первое лицо будет решено 1/6, и поэтому 5/6 частей придется перемещать. Второе лицо будет решено на 1/5 и потребует 4/5 изделий для перемещения. Третье лицо 3/4, четвертое лицо 2/3, пятое лицо 1/2 и последнее лицо будет полностью решено. Среднее количество движений (k) для перемещения отдельной части может быть оценено экспериментально как ~ 2,1. Значение k уменьшается с увеличением размера куба. Значение никогда не может быть менее 2, поскольку коммутатор требует, чтобы каждый кусок был перемещен не менее 2 раза.
Этот алгоритм оптимизирован для очень больших кубиков. Однако это ужасно для маленьких кубиков. Основные оптимизации были сосредоточены на решении центров как можно быстрее, и не было рассмотрено никакого рассмотрения для решения краев. Однако размер краев незначителен по сравнению с центрами по мере увеличения размера куба. На приведенном ниже графике показано, как среднее количество движений на часть уменьшается с большими кубиками. Примечание: это не график k. Это график (общий ход) / (количество кусочков)
cmake -B build -S .
cd build
cmake --build .
RCube/RCube
