Как заставить этот код пролога работать в разумное время?

Question

Недавно я столкнулся с математической головоломкой, которая выглядит следующим образом:

Представьте себе 13 конвертов, каждый из которых пронумерован от 1 до 13. Возьмите 13 учетных карточек, пронумерованных от 528 до 540. Найдите возможное расположениекарты в конвертах, так что число на каждой карте можно разделить на содержащий конверт без остатка.

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

Я не знаю, как сделать это разумно в прологе. Мне удалось только сделать грубую силу, то есть проверить каждый возможный порядок

valid([], []).
valid([EHEAD|ETAIL], [CHEAD|CTAIL]) :- 0 is mod(EHEAD, CHEAD), valid(ETAIL, CTAIL).

numlist(1,13,Envelopes),
permutation(Contents, C), numlist(528, 540, C),
valid(Contents, Envelopes).

Это решение не работает в разумное время, поэтому я не могу его проверить (но оно выглядит о праве). Как я могу заставить его вернуться назад, например, я инстинктивно знаю, что бесполезно искать решения, которые пытаются связать нечетное число с любым четным числом (и это обобщает все номера конвертов), но не знают, как это реализовать.

Answer 1

Просто используйте недетерминизм, здесь представленный как выберите / 3:

:- module(p13, [p13/1]).

p13(L) :-
    numlist(1,13,Envelopes),
    numlist(528,540,Cards),
    associate(Cards,Envelopes,L).

associate([],[],[]).
associate([Card|Cards],Envelopes,[Card/Env|Rest]) :-
    select(Env,Envelopes,Envelopes1),
    Card mod Env =:= 0,
    associate(Cards,Envelopes1,Rest).

выход

?- p13(L).
L = [528/4, 529/1, 530/10, 531/9, 532/7, 533/13, 534/6, 535/5, ... / ...|...] .

Answer 2

Типичным вариантом было бы использовать программирование логики ограничений по конечным доменам, т.е. для краткости CLP (FD). Особенности будут зависеть от того, какой Пролог вы используете. С SWI-Prolog мы могли бы решить эту проблему следующим образом:

:- use_module(library(clpfd)).

envelope(Num, envelope(Num, _)).

index(envelope(Num, Index), Index) :-
    Index in 528..540,
    Index rem Num #= 0.

solve(Envelopes) :-
    % Start by constructing a list of 13 `envelope(Number, Index)` structures.
    numlist(1, 13, Numbers),
    maplist(envelope, Numbers, Envelopes),
    % Constrain each index to be an integer in 528..540, and to be
    % divisible by the number of the envelope. Also collect the Index
    % variables into a list for use below.
    maplist(index, Envelopes, IndexVars),
    % Constrain all Index variables to have a different value.
    all_different(IndexVars),
    % Find values for the indices.
    label(IndexVars).

Мы можем найти решение и распечатать его в удобочитаемой форме:

?- time(solve(Envelopes)), 
   forall(member(envelope(Num, Index), Envelopes), 
          format("Envelope ~d: ~d~n", [Num, Index])).
% 59,435 inferences, 0.000 CPU in 0.005 seconds (0% CPU, Infinite Lips)
Envelope 1: 529
Envelope 2: 538
Envelope 3: 537
Envelope 4: 528
Envelope 5: 535
Envelope 6: 534
Envelope 7: 532
Envelope 8: 536
Envelope 9: 531
Envelope 10: 530
Envelope 11: 539
Envelope 12: 540
Envelope 13: 533
Envelopes = ...