Пример 10.6. Модель удовлетворения ограничений для задачи SEND MORE MONEY

Студент посылает домой закодированную телеграмму:

SEND

+MORE

________

MONEY

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

Заметим, что эта задача может быть записана с помощью модели цело­численного программирования (ЦП), но она содержит около сотни целочис­ленных переменных, причем эта модель ЦП трудна для решения с помощью классических подходов ЦП, таких, как алгоритмы ветвей и границ.

В то же время логический анализ задачи позволяет найти ее решение. Так, замечая, что ни , ни не могут быть нулями, получим: . Далее, единственной возможностью для является значение 1, т.е. . Затем, из равенства получаем, что может быть равно только 9. Можно показать, что символу соответствует цифра 0, т.е. . Далее, пере­ходя к сотням, из и условия, что и должны быть разичными, получим . Продолжая аналогичным образом логический анализ ограничений, найдем решение задачи: .

Основная сложность этой задачи состоит в необходимости учета огра­ничения «все цифры различны» (так называемое глобальное ограничение all-different).

Запишем ограничения задачи.