Требуется расшифровать запись арифметического равенства, в котором цифры заменены буквами, причем разные цифры заменены разными буквами, одинаковые - одинаковыми. Предполагается, что исходное равенство верно и записано по обычным правилам арифметики. В частности, в записи числа первая слева цифра не является цифрой 0; используется десятичная система счисления. Ввести ребус в формате ЧИСЛО+ЕЩЕ=СУММА, вывести в столбик все решения в строковом лексикографическом порядке.
ЧИСЛО+ЕЩЕ=СУММА
29348+767=30115 29368+747=30115 59638+474=60112 59678+434=60112 69714+838=70552 69734+818=70552
Спойлер: как я решал эту задачу. Сначала я, конечно, написал решение «в лоб», которое (после ввода и подготовки данных) начиналось строкой
Этого достаточно, чтобы любой пример решался секунд за 10.
Но можно пойти чуть дальше:
Можно решать так, как вообще решают такие примеры. Подставлять все возможные цифры в младшие разряды слагаемых и делать выводы относительно соответствующих цифр в сумме. Например, из того, что последняя цифра первого слагаемого равна 1, а второго — 2, следует, что последняя цифра сумы равна 3.
Вот рекурсивный алгоритм, в котором рекурсия идёт по множеству (словарю, конечно) подстановок вида «буква→цифра»:
Если в сложении цифровых хвостов есть значащая цифра, а в сумме в этом месте стоит буква, то она должна равняться этой цифре
Может оказаться, что значащая цифра есть, а подстановка невозможна (например, эта цифра уже соответствует другой букве). Если это так,