По следам криптарифмов
АрхивПравда, в голове у меня теперь полно всяких мыслей... только вот о чем они - не знаю!
Л. Кэрролл. "Алиса в Зазеркалье"
Видимо, мне удалось задеть-таки любителей программирования за живое. На мою статью "Криптарифмы" ("Компьютерра" #50 (227) от 15 декабря 1997 года) пришло много самых разнообразных откликов. В частности, мне прислали пять или шесть программ, решающих разные криптарифмы. Так что свою задачу-минимум я, можно сказать, выполнил. А раз тема "пришлась ко двору", можно развивать ее дальше.
Размышления об алгоритмах
Несколько читателей, кроме программ, поделились своими мыслями об алгоритмах решения криптарифмов. Увы, кажется, никто не реализовал ничего похожего на "человеческий" способ решения таких задач. Ведь как мы, например, начинаем решать ребус "РЮМКА+РЮМКА=СТОПКА"? Естественно, с последнего столбца: раз А+А=А, то А=0. Аналогично тут же получается, что и К=0. Значит, такой криптарифм не имеет решений (ведь разными буквами должны быть зашифрованы разные цифры)! Похожие рассуждения почти всегда применяются в самых разных ребусах-криптарифмах, и именно благодаря им человек способен справиться со сложными задачами, сведя дело к очень небольшому перебору.
Однако все машинные алгоритмы поиска решений сводятся обычно к рекурсии и перебору всех возможных перестановок букв по множеству цифр от 0 до 9. Количество таких перестановок равно 10!=3628800, так что "Пентиум" справляется с перебором за считанные секунды, но решение сотни ребусов уже требует значительного времени даже от быстрых компьютеров.
Читатели выдали несколько идей, позволяющих избавиться от рекурсии с перебором вариантов. Я процитирую только одно письмо - его автор Денис Коновальчик из Магнитогорска (он, кстати, автор нескольких статей, опубликованных в "Компьютерре", и победитель одного из наших юмористических конкурсов):
"Естественно, как программист с дипломом, я поначалу набросал стандартный алгоритм с возвратом для перебора цифровых значений всех букв и проверки получившейся суммы в самом "глубоком" вхождении в рекурсию и тут же его отбросил - уж слишком медленно все это работало.
Необходимо было упростить процедуру проверки. Тогда, обратившись к первому примеру из Вашей статьи, я получил следующее:
USA+USSR=PEACE 100*U+10*S+A+1000*U+100*S+10*S+R-10000*P-1000*E-100*A-10*C-E=0, или: 1100*U+120*S-99*A+R-10000*P-1000*E-10*C-E=0
Проверить такое равенство на истинность значительно проще, чем переводить каждый раз буквы в цифры в теле глубокой рекурсии. Более того, при таком способе проверки для каждого уровня рекурсивной вложенности можно уже вести подсчет частично накопленной на предыдущих уровнях суммы, что избавляет от лишних подсчетов. Эта идея и была реализована в предлагаемой мною программе".
Но все-таки лучше и быстрее других работает программа, написанная Сергеем Никитиным, аспирантом Омского университета. Я не стал дотошно копаться в ее алгоритме, но готов предоставить такую возможность всем желающим. (Сергей написал в документации к своей программе, что она является свободно копируемой и свободно изменяемой. Так что все желающие могут получить архив с исходниками и исполняемым модулем от меня по электронной почте. Присылайте заявки.)
Программа Сергея, кроме традиционного способа записи условия (с суммой нескольких слагаемых), понимает и другие. Например, ребус "SIX+SIX+SIX=NINE+NINE" можно записать, опустив знаки сложения ("SIX SIX SIX=NINE NINE"), или же заменив их умножением на число ("3*SIX=2*NINE"), или опустив в последнем варианте знаки умножения ("3 SIX=2 NINE"). Или даже "3six-2nine" - пробелы, как и знаки умножения, программа вставит сама, а полученное выражение по умолчанию будет приравнено нулю!
Сергей Никитин прислал также два правильных русских ребуса на двойное сложение: 37. СЕМЬ+СЕМЬ+ОДИН=5*ТРИ; 38. 60*ПЯТЬ=ТРИСТА (я продолжил нумерацию из моей первой статьи о криптарифмах.)
"Хвосты"
Вернусь к тем криптарифмам, которые были опубликованы в моей подборке. Некоторые из них оказались неправильными, то есть допускали довольно большое число различных решений. Так, ребус "РАЙОН+РАЙОН=ГОРОД" имеет два решения, "ДЕДКА+БАБКА+РЕПКА=СКАЗКА" - четыре, а "ЛАДЬЯ+ЛАДЬЯ+ФЕРЗЬ" - целых шестнадцать! Тем же недостатком страдает и фраза-криптарифм "Merry xmas from Maxey" - у нее 24 различных решения.
Я не смог удержаться от соблазна привести несколько новых криптарифмов, найденных мною с использованием программ-решалок.
Новые задачи
39. ШАХ+ШАХ+ШАХ+ШАХ+ШАХ+ШАХ=МАТ(6*ШАХ=МАТ);
40. 7*ШАХ=МАТ;
41. 7*СЛОВО=ФРАЗА;
42. 27*СЛОВ=ФРАЗА;
43. 4*ОДИН=МНОГО;
44. 6*ОДИН=МНОГО;
45. КОМПЬ*Ю=ТЕРРА.
Несколько читательских идей порадовали меня еще больше, чем присланные программы. Больше всего запомнилась идея того же Дениса Коновальчика:
"Промелькнула в Вашей заметке идея о том, что неплохо бы желающим написать программку для "расщелкивания" криптарифмов. В принципе, это действительно неплохая "школа" для начинающих. Но, с другой стороны, может быть, стоит тем, кто считает себя "профи", создать программу, преследующую прямо противоположную цель, а именно: создать криптарифмы на базе словаря из некоторого множества слов, связанных по смыслу. Естественно, компьютер только генерирует все возможные варианты, а уж оценить их остроумие - удел человека. Сложность этой задачи, конечно, на порядок выше, но и решать ее намного интереснее. А уж для Вас как коллекционера она и вовсе может иметь исключительный интерес. Так что, может стоит объявить нечто вроде неформального читательского конкурса на самую оптимальную программу такого рода?"
Итак,
Серьезная задача 1. Дан входной словарь (входящие в него слова мы здесь обозначим заглавными буквами латинского алфавита), нужно получить все возможные правильные криптарифмы вида: а) A+B=C, б) A+B+C=D, в) аналогичные суммы большей длины (скажем, до некоторого предела, который можно задавать на входе программы), г) n*A+m*B=C, где n и m - натуральные числа. Напоминаю, что правильными считаются криптарифмы, имеющие единственное решение.
Серьезная задача 2. Дан криптарифм (для простоты, пусть он имеет вид A+B=C). Написать программу, которая решает его "человеческим" способом - то есть не перебирая все дерево вариантов, а отсекая тупиковые ветви путем использования разнообразных свойств делимости и т. п.
Свои предложения, решения, заявки присылайте мне по адресу kk@knop.spb.ru. Я постараюсь ответить на все пришедшие письма.
