Пролог криптарифметического умножения

У меня есть понимание идеи арифметики склепа и сложения, но я не могу понять, как решить арифметическую задачу с умножением. Это просто ДВА * ШЕСТЬ = ДВЕНАДЦАТЬ или что-то в этом роде без средней дополнительной части задачи на умножение. Я ничего не смог найти в Интернете, и я уже нашел некоторые ограничения для проблемы, но ничто не привело меня к некоторым ответам. Не знаю, где спросить об этом, и подумал, что это будет лучшее место.

Я хочу знать, как решить арифметическую задачу с умножением.

Я уже сделал вывод:

         T  W  O
*        S  I  X
_________________
T  W  E  L  V  E


T \= 0 which also means S \= 0
T is 1-6
E is (O*X) mod 10
O or X cannot be 0 or 1 since E has to be different and 0 or 1 gives the same value 
as either O or X.

РЕДАКТИРОВАТЬ: я использовал метод генерации и тестирования

solve(T,W,O,S,I,X,E,L,V) :-
        X = [T,W,O,S,I,X,E,L,V],
        Digits = [0,1,2,3,4,5,6,7,8,9],
        assign_digits(X, Digits),
        T > 0, 
        S > 0,
        100*T + 10*W + O * 100*S + 10*I + X =:=
        100000*T + 10000*W + 1000*E + 100*L + 10*V + E,
        write(X).

select(X, [X|R], R).
select(X, [Y|Xs], [Y|Ys]):- select(X, Xs, Ys).

assign_digits([], _List).
assign_digits([D|Ds], List):-
        select(D, List, NewList),
        assign_digits(Ds, NewList).

math prolog cryptarithmetic-puzzle
person user2318083    schedule 16.05.2014    source источник
comment
Четко сформулируйте свой вопрос. Также проверьте, не является ли это тем, что вы ищете: stackoverflow.com/questions/23575795/   -  person Grzegorz Adam Kowalski    schedule 16.05.2014
comment
Я его туда выложил, но просто хочу знать, как решить проблему хотя бы на бумаге. Я не знаю, как это сделать, и проблема сложения проста. Та ссылка, которую вы разместили, является дополнительной проблемой, и я понимаю это.   -  person user2318083    schedule 16.05.2014

Ответы (2)


arrow_upward
6
arrow_downward

Тривиально делать с программированием логики ограничений. Например, в прологе ECLiPSe:

:- lib(ic).
puzzle(Vars) :-
    [T,W,O,S,I,X,E,L,V] = Vars,
    Vars :: 0..9,
    alldifferent(Vars),
    T #> 0, S #> 0,
    (100*T + 10*W + O) * (100*S + 10*I + X) #= 
      100000*T + 10000*W + 1000*E + 100*L + 10*V + E,
    labeling(Vars).

Первое решение:

[eclipse]: puzzle([T,W,O,S,I,X,E,L,V]).
T = 1
W = 6
O = 5
S = 9
I = 7
X = 2
E = 0
L = 3
V = 8
Yes (0.01s cpu, solution 1, maybe more) ?

Есть 3 разных решения:

[eclipse]: puzzle([T,W,O,S,I,X,E,L,V]), writeln([T,W,O,S,I,X,E,L,V]), fail.
[1, 6, 5, 9, 7, 2, 0, 3, 8]
[2, 1, 8, 9, 6, 5, 0, 3, 7]
[3, 4, 5, 9, 8, 6, 0, 1, 7]
No (0.02s cpu)

Обновление — перевод в SWI Prolog:

:- use_module(library(clpfd)).
puzzle(Vars) :-
    [T,W,O,S,I,X,E,L,V] = Vars,
    Vars ins 0..9,
    all_different(Vars),
    T #> 0, S #> 0,
    (100*T + 10*W + O) * (100*S + 10*I + X) #= 
      100000*T + 10000*W + 1000*E + 100*L + 10*V + E,
    label(Vars).
person Sergii Dymchenko    schedule 16.05.2014
comment
Не слишком знаком с прологом eclipse, и я делаю это в прологе swi. Можете ли вы объяснить, что такое labeling(Vars)., all different(Vars). и lib(ic)? - person user2318083; 16.05.2014
comment
@ user2318083 Я добавил перевод в SWI-Prolog. Смотрите мой обновленный ответ. См. документацию по clpfd swi-prolog.org/pldoc/man?section=clpfd для получения дополнительной информации. - person Sergii Dymchenko; 16.05.2014
comment
Спасибо, это действительно помогло. Я подходил к этому по-другому с генерацией и тестом. Я редактировал его с помощью своего кода, но он всегда возвращает false. Я не уверен, почему, было бы возможно, если бы вы могли просмотреть мой код там? - person user2318083; 17.05.2014
comment
@ user2318083 в вашем коде есть две проблемы, которые легко исправить. Первая проблема, в X = [T,W,O,S,I,X,E,L,V], вы выбрали имя X для списка всех переменных, но у вас уже есть переменная с именем X! Вторая проблема — отсутствие скобок в 100*T + 10*W + O * 100*S + 10*I + X. После исправления этих ошибок ваш код работает нормально. - person Sergii Dymchenko; 17.05.2014

arrow_upward
3
arrow_downward

Более общее решение без CLP:

number_to_digits(Number,List) :-
        length(List,Len),
        ntb(0,Len,Number,List).

ntb(N,_,N,[]).
ntb(C,E,N,[D|L]) :-
        NE is E-1,
        V is C + D*10^NE,
        ntb(V,NE,N,L).

crypto(In1, In2, Out) :-
    term_variables([In1, In2, Out], Vars),
    permutation([0,1,2,3,4,5,6,7,8,9], Perm),
    append(_, Vars, Perm),
        number_to_digits(N1, In1),
        number_to_digits(N2, In2),
        number_to_digits(N3, Out),
        N3 is N1 * N2.

Это довольно неэффективно, и определенно эту проблему следует решать с помощью CLP, как это сделал @Sergey, но, возможно, кого-то заинтересуют возможные решения без CLP.

Вход и выход:

?- crypto([T,W,O], [S,I,X], [T,W,E,L,V,E]).
T = 0,
W = 5,
O = 7,
S = 9,
I = 6,
X = 2,
E = 4,
L = 8,
V = 3;
(...)

(57 * 962 = 54834).

person Grzegorz Adam Kowalski    schedule 17.05.2014