ДОНАЛД + ГЕРАЛД = РОБЕРТ, или Как перевести арифметический ребус?

Question

[Mercury13]

Вот такой арифметический ребус я обнаружил в старой советской книге. Очевидно, что это какой-нибудь Дьюдени или Гарднер, DONALD + GERALD = ROBERT, быстро и коряво локализованный на русский. И сразу возникла такая задача.

Есть словарь. Какие есть способы эффективно подобрать три русских слова с той же раскладкой букв (желательно — все возможные тройки)? Какая предобработка нужна такому словарю?

Напоминаю правила арифметического ребуса. Здесь верный арифметический пример, каждая цифра заменена буквой, одинаковые буквы — одинаковые цифры, разные буквы — разные цифры.

Answer 1

[Андрей]

Мне видится следующий путь ускорения поиска:
1) убираем все символы встречающиеся только один раз - только на финальном этапе придется проверить у подобранной тройки не нарушение уникальности выброшенных букв между собой и между выброшенными и оставленными; получаем условно DO*ALD+*ERALD=RO*ER*
2) выбираем слово с наибольшим количеством оставшихся символов и начинаем путешествие по словарю; для каждого потенциального кандидата на первое слово ищем кандидатов для второго и третьего проверяя совпадение оставшихся букв и уникальность отброшенных.

Для ускорения поиска я бы создал массив NxNxK, где N - колво слов длины K в словаре и поднимал в нем в позиции K для буквы в первом слове биты позиций этой же буквы во втором слове. Этот же массив мог бы помочь в поиске первоначальных претендентов для первого слова (анализировать необходимо ячейки [i,i,*])