Программирование на языке ПРОЛОГ для искуственного интеллекта



Тимофей Кургин

Решение числового ребуса с использованием nonvar


Известным примером числового ребуса является

+ D O N A L D
G E  R A L D
R O B  E R T

Задача состоит в том. чтобы заменить буквы D, О, N и т.д. на цифры таким образом, чтобы вышеприведенная сумма была правильной. Разным буквам должны соответствовать разные цифры, иначе возможно тривиальное решение, например, все буквы можно заменить на нули.

Определим отношение

        сумма( Nl, N2, N)

где Nl, N2 и N представляют три числа данного ребуса. Цель cyммa(Nl, N2, N) достигается, если существует такая замена букв цифрами, что N1+N2 = N.

Первым шагом к решению будет выбор представления чисел Nl, N2 и N в программе. Один из способов - представить каждое число в виде списка его цифр. Например, число 255 будет тогда представляться списком [2, 2, 5]. Поскольку значения цифр нам не известны заранее, каждая цифра будет обозначаться соответствующей неинициализированной переменной. Используя это представление, мы можем сформулировать задачу так:

        [ D, O, N, A, L, D ]
  +    [ G,  E, R, A, L, D ]
  =    [ R, О, B,  E, R, T ]

Теперь задача состоит в том. чтобы найти такую конкретизацию переменных D, О, N и т.д., для которой сумма верна. После того, как отношение сумма будет запрограммировано, задание для пролог-системы на решение ребуса будет иметь вид

        ?-  сумма( [D, O, N, A, L, D], [G, E, R, A, L, D],
                           [R, O, В, Е, R, T ).

       

fig7_1.gif (2230 bytes)

Рис. 7. 1.  Поразрядное сложение.    Отношения в показанном i-м
разряде такие:    D3i = (C1 + D1i + D2i)     mod    10;    C = (C1 + D1i + D2i)
div  10  (div - целочисленное деление,   mod - остаток от деления).




Содержание  Назад  Вперед