Криптограмма-головоломка с прологом CLPFD

Question

Недавно я нашел небольшую игру в магазине приложений Google Play под названием Cryptogram. Есть десятки приложений, похожих на это. Идея состоит в том, чтобы сопоставить число с цветами, чтобы все уравнения звучали правдоподобно.

Мне удалось довольно быстро справиться с проблемами 1-8 и 10, но проблема 9 оказалась для меня более сложной.

Задача 9

Через некоторое время, пытаясь угадать, я сдался и решил запрограммировать решение. Я использовал Prolog/Datalog для некоторых небольших задач в качестве старшекурсника, а также для некоторых задач Project Euler. Ранее я видел 15-строчный решатель судоку, использующий библиотеку Prolog's Constraint Logic Program для конечных доменов (clpfd), и решил сам попробовать. Я использую SWI-Prolog.

:- use_module(library(clpfd)).
problem(Colors) :-
    Colors = [Pink, Cyan, Yellow, Green, Purple, Red, Brown, White, Lime],
    Colors ins 0..9,
    all_distinct(Colors),
    % The leading digit of a number can't be 0
    Pink #\= 0,
    Red #\= 0,
    White #\= 0,
    Green #\= 0,
    Lime #\= 0,
    Cyan #\= 0,
    % I originally tried to write a predicate generalizing numbers and a list of digits
    % but got in way over my head with CLPFD.
    Number1_1 #= (Pink * 1000) + (Cyan * 100) + (Pink * 10) + Yellow,
    Number1_2 #= (Green * 10) + Purple,
    Number1_3 #= (Cyan * 100) + (Red * 10) + Purple,
    Number2_1 #= (Red * 1000) + (Brown * 100) + (White * 10) + Red,
    Number2_2 #= (Lime * 10) + Yellow,
    Number2_3 #= (Red * 1000) + (Lime * 100) + (Purple * 10) + Pink,
    Number3_1 #= (White * 1000) + (Purple * 100) + (Cyan * 10) + White,
    Number3_2 #= (Green * 1000) + (Cyan * 100) + (Yellow * 10) + Purple,
    Number3_3 #= (Cyan * 1000) + (Red * 100) + (Yellow * 10) + Red,
    % I'm not 100% sure whether to use floored or truncated division here.
    % I thought the difference would be a float vs integer output,
    % but that doesn't make sense with finite domains.
    Number1_1 // Number1_2 #= Number1_3,
    Number1_1 rem Number1_2 #= 0,
    Number2_3 #= Number2_1 + Number2_2,
    Number3_3 #= Number3_1 - Number3_2,
    Number3_1 #= Number1_1 - Number2_1,
    Number3_2 #= Number1_2 * Number2_2,
    Number3_3 #= Number1_3 + Number2_3.

Вывод, когда я запускаю этот запрос в SWI-Prolog, заставляет меня чувствовать, что я неправильно понимаю большую концепцию в CLPFD:

?- problem([Pink, Cyan, Yellow, Green, Purple, Red, Brown, White, Lime]).
Pink in 3..9,
_7756#=Pink+10*Purple+1000*Red+100*Lime,
_7810#=1010*Pink+100*Cyan+Yellow,
all_distinct([Pink, Cyan, Yellow, Green, Purple, Red, Brown, White|...]),
Cyan in 1..7,
_7946#=1000*Cyan+10*Yellow+101*Red,
_7994#=100*Cyan+10*Yellow+1000*Green+Purple,
_8048#=10*Cyan+100*Purple+1001*White,
_8096#=100*Cyan+Purple+10*Red,
Yellow in 0..9,
_8162#=Yellow+10*Lime,
Green in 1..7,
_8216#=10*Green+Purple,
Purple in 0..9,
Red in 1..7,
_8294#=1001*Red+100*Brown+10*White,
Brown in 0..9,
White in 2..8,
Lime in 1..9,
_7756 in 1103..7568,
_8096+_7756#=_7946,
_8294+_8162#=_7756,
_8096 in 110..779,
_7810//_8216#=_8096,
_7810 in 3334..9799,
_8048+_8294#=_7810,
_7810 rem _8216#=0,
_8048 in 2313..8778,
_7946+_7994#=_8048,
_7946 in 1213..7678,
_7994 in 1100..7565,
_8216*_8162#=_7994,
_8216 in 12..79,
_8162 in 14..99,
_8294 in 1021..7486.

Я ожидаю, что каждый цвет в списке цветов будет привязан к одному отдельному целому числу в диапазоне 0,9, но это не то, что происходит. Можете ли вы помочь мне найти решение этой проблемы?

РЕДАКТИРОВАТЬ

Поэтому я выбрал произвольный цвет и начал присваивать ему номера в диапазоне, который, по словам ограничения, должен быть действительным. Я выполнил этот запрос с Cyan, привязанным к 1.

?- problem([Pink, 1, Yellow, Green, Purple, Red, Brown, White, Lime]).
false.

Что не имеет смысла. Предыдущий "вывод" говорит "Cyan in 1..7", что, как я думал, означало, что любое значение в этом диапазоне является действительным. Однако, если я выберу другое произвольное значение для Cyan:

?- problem([Pink, 2, Yellow, Green, Purple, Red, Brown, White, Lime]).
Pink = 7,
Yellow = 6,
Green = 3,
Purple = 4,
Red = 1,
Brown = 8,
White = 5,
Lime = 9.

Я получаю ответ, который искал. Хотя криптограмма решена, я до сих пор не понимаю, почему библиотека Prolog CLPFD не нашла ее полностью независимо.

РЕДАКТИРОВАТЬ 2

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

:- use_module(library(clpfd)).

digit_number(0, [], 1).

digit_number(Number, [Digit|Tail], DigitPlace) :-
    digit_number(NextNumber, Tail, NextDigitPlace),
    DigitPlace #= NextDigitPlace * 10,
    PlaceNumber #= Digit * (NextDigitPlace),
    Number #= PlaceNumber + NextNumber.

digit_number(Number, ColorList) :-
    digit_number(Number, ColorList, _).

problem(Colors) :-
    Colors = [Pink, Cyan, Yellow, Green, Purple, Red, Brown, White, Lime],
    Colors ins 0..9,
    all_distinct(Colors),
    digit_number(Number1_1, [Pink, Cyan, Pink, Yellow]),
    digit_number(Number1_2, [Green, Purple]),
    digit_number(Number1_3, [Cyan, Red, Purple]),
    digit_number(Number2_1, [Red, Brown, White, Red]),
    digit_number(Number2_2, [Lime, Yellow]),
    digit_number(Number2_3, [Red, Lime, Purple, Pink]),
    digit_number(Number3_1, [White, Purple, Cyan, White]),
    digit_number(Number3_2, [Green, Cyan, Yellow, Purple]),
    digit_number(Number3_3, [Cyan, Red, Yellow, Red]),
    Number1_1 // Number1_2 #= Number1_3,
    Number1_1 rem Number1_2 #= 0,
    Number2_1 + Number2_2 #= Number2_3,
    Number3_1 - Number3_2 #= Number3_3,
    Number1_1 - Number2_1 #= Number3_1,
    Number1_2 * Number2_2 #= Number3_2,
    Number1_3 + Number2_3 #= Number3_3,
    label(Colors).

Answer 1

Другой ответ показывает вам один из способов получить желаемый результат, но я хотел бы ответить на некоторые ваши вопросы.

Я до сих пор не понимаю, почему библиотека Пролога CLPFD не нашла его полностью независимо.

Prolog - это более или менее декларативный язык программирования, но (хотя мы хотим притворяться, из соображений пропаганды), вы не можете просто записать что-либо, что логически эквивалентно вашей проблеме, и ожидать, что оно будет выполнено правильно и эффективно. В частности, порядок выполнения различных целей имеет большое значение, хотя это и не должно иметь никакого логического значения. Это особенно верно для арифметики. Рассматривать:

?- between(1, 99999999, N), N > 99999998.
N = 99999999.  % correct but slooooow

?- N > 99999998, between(1, 99999999, N).
ERROR: >/2: Arguments are not sufficiently instantiated

Делать то же самое с CLP(FD) работает намного приятнее:

?- N in 1..99999999, N #> 99999998.
N = 99999999.  % correct and fast!

?- N #> 99999998, N in 1..99999999.
N = 99999999.  % also correct, also fast!

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

Чтобы достичь этого, в отличие от обычного Пролога, CLP(FD) отделяет набор ограничений от фактического поиска решений. Поскольку ваша программа развивается и создает ограничения, CLP(FD) сделает некоторые упрощения, как в вашем примере, где она определяет Cyan in 1..7 самостоятельно или в моем примере выше, где он может найти уникальное решение немедленно. Но в целом эти упрощения не решают проблему полностью.

Одной из причин этого является просто производительность: поиск может быть медленным. Это может быть быстрее, если известно больше ограничений, потому что новые ограничения для уже ограниченных переменных могут только сделать пространство поиска меньше, но никогда не увеличиваться! Имеет смысл отложить это до тех пор, пока конкретные ответы не потребуются.

По этой причине для получения конкретных результатов необходимо вызвать предикат маркировки, который систематически перечисляет решения. В SWI-Прологе простые indomain/1 а также label/1; общий labeling/2, Этот последний даже позволяет вам влиять на стратегию исследования пространства поиска, которая может быть полезна, если у вас есть некоторое понимание предметной области.

Предыдущий "вывод" говорит "Cyan in 1..7", что, как я думал, означало, что любое значение в этом диапазоне является действительным.

Не совсем: это означает, что если есть правильное решение для Cyan тогда он находится в диапазоне от 1 до 7. Это не дает гарантии, что все значения в этом диапазоне являются решениями. Например:

?- X in 1..5, Y in 1..5, X #< Y.
X in 1..4,
X#=<Y+ -1,
Y in 2..5.

3 находится в диапазоне 1..4 и 3 находится в диапазоне 2..5, так что чисто исходя из этого, мы могли бы ожидать решения с X = 3 а также Y = 3, Но это невозможно из-за дополнительного ограничения. Только маркировка фактически даст вам ответы, которые являются гарантированными решениями, и только если вы пометите все переменные в запросе.

Смотрите также очень хороший ответ здесь: /questions/17753469/ya-ne-ponimayu-chto-delaet-yarlyik-v-prologe/17753479#17753479

Редактировать:

% I'm not 100% sure whether to use floored or truncated division here.
% I thought the difference would be a float vs integer output,
% but that doesn't make sense with finite domains.
Number1_1 // Number1_2 #= Number1_3,

Действительно, дробное деление здесь не имеет смысла, но Пролог сказал бы вам:

?- X in 1..5, Y in 1..5, Z #= X // Y.
X in 1..5,
X//Y#=Z,
Y in 1..5,
Z in 0..5.

?- X in 1..5, Y in 1..5, Z #= X / Y.
ERROR: Domain error: `clpfd_expression' expected, found `_G6388/_G6412'

Answer 2

Ваш код работает, просто добавьте метку (C):

?- problem(C), label(C).
C = [7, 2, 6, 3, 4, 1, 8, 5, 9] .