Некоторые мысли о программировании решения кубика РубикаДисклаймер. Многие фрагменты я делал, кубик крутил, переборы делал, табулировал и все остальное, но вот целиком все это, то что опишу, не делал, так что возможны подводные грабли: гладко было на экране, но забыли про... хмм... мы о кране, что ли? СНИЖЕНИЕ ГЛУБИНЫ ПЕРЕБОРА ВСТРЕЧНЫМ ПЕРЕБОРОМ
Используется когда известна максимальная глубина перебора.
Поскольку перебор у нас растет как степень, то снижение глубины вдвое полностью меняет дело, она может оказаться вполне достижимой.
Стратегия такая:
а) пусть у нас максимальная глубина 16. будем перебирать 8 поворотов и запоминать все полученные позиции.
б) начинаем с конца, делаем повороты и смотрим вышли ли мы на одну из запомненных позиций. если да, задача решена.
КАК ЗАПОМИНАТЬ ВСЕ ПОЗИЦИИ, ЕСЛИ В ПАМЯТЬ НЕ ПОМЕЩАЮТСЯ
а) Есть такой алгоритм поиска который определяет что данное слово возможно есть в базе и можно точно сказать, что слова нет.
Заводим довольно большой битовый массив из нулей длиной N. Назовем его контрольный массив.
По каждому слову считаем хэш-сумму. В нашем случае будем считать хэш от позиции на кубике.
И получив хэш сумму, используем ее как затравку для генерации 3-х чисел (допустим) от 0 до N-1. В контрольном массиве по данным индексам проставляем 1.
Итак, когда мы получили все возможные слова, у нас в массиве должно быть не более половины 0 и 1 на случайных местах.
***
Как определяем, что данное слово возможно встречалось. Генерим 3 его позиции единиц по хэш сумме. И смотрим в контрольном массиве. Если на указанных местах есть хотя бы один 0, то отказ, слово такое не встречалось.
Если все три 1, то слово возможно встречалось.
б) Нестрогое определение того, что данная позиция нам встречалась будет приводить иногда к ложным срабатываниям, но львиную долю проверок отсечет. При этом память может быть использована более чем разумно.
НЕТОЧНЫЙ ПРОСЧЕТ
в) Как ускорить перебор. Дело в том, что опять же нам не обязательно прослеживать КАЖДЫЙ элемент на кубике. В классическом кубике 3х3х3 у нас 20 подвижных элементов. Но мы можем просчитывать повороты не всех элементов, а, допустим, 4 угла и 4 ребра, так чтобы у нас все это дело влезало в удобное представление в памяти, например в 64-битное число.
И вот только если 4 наших контрольных угла и 4 ребра встали в искомое положение, мы подозреваем, что это хороший набор поворотов и теперь проверяем его уже тщательно, используя проверку всех 20 элементов.