Двунаправленное решение задачи сборки кубика Рубика с использованием радужных таблиц

В современных научных работах по вычислительному решению задачи приводятся оценки срока поиска решения порядка 8 ядро-лет. Предложенная методика, по предварительным оценкам, примерно на 2 порядка эффективнее и позволит находить решения не только на суперкомпьютерах, но и на любом ноутбуке.

Первая особенность метода — подход к задаче сразу с двух концов. Вместо того, чтобы строить полное дерево перебора ходов, содержащее порядка 10^25 элементов, строится два дерева по 10^12 элементов, что даёт экономию памяти в биллион раз. Первое дерево строится от собранного кубика, второе — от условия задачи. Затем сравниваются конечные листы этих деревьев.

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

??спользование радужной таблицы подкреплено следующей аналогией: последовательность ходов подобна паролю, а состояние кубика подобно хэш-функции от последовательности ходов. Потому что зная последовательность ходов, можно легко вычислить состояние кубика, а обратная задача сложна вычислительно. Восстановление пароля по хэшу — это как раз та область, в которой радужные таблицы наиболее эффективны в плане времени вычислений и занимаемой памяти. А разбиение пути решения на два встречных потока позволит не только сделать первую половину решения всего 1 раз, но и позволит поместить радужную таблицу на жёстком диске обычного компьютера.

??сходя из этого, алгоритм «сборки» кубика такой.
1. ??щем состояние кубика в радужной таблице.
2. Если не находим — делаем полный перебор 18 вариантов одного хода (либо случайный ход при использовании метода Монте-Карло). ??щем новые варианты в радужной таблице.
3. Повторяем шаг 2 до получения решения.

Предварительные расчёты показывают, что для радужной таблицы понадобится жёсткий диск объёмом не менее 1 тб — такие уже не редкость. ??спользование распределённых радужных таблиц серьёзно уменьшит требования к ресурсам.

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