Блог

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

Грязный ребенок написал задачу на умножение.

1. Алиса увидела 100 x 6.
2. Боб увидел 101 x 6.
3. Дэн увидел 102 x 9.

Каждый только неправильно прочитал цифру. Каково реальное решение проблемы?

Моей первой мыслью было определить отношение: «Человек увидел цифру в позиции»:

 saw(alice, 1, 0).
saw(alice, 0, 1).
saw(alice, 0, 2).
saw(alice, 6, 3).

saw(bob, 1, 0).
saw(bob, 0, 1).
saw(bob, 1, 2).
saw(bob, 6, 3).

saw(dan, 1, 0).
saw(dan, 0, 1).
saw(dan, 2, 2).
saw(dan, 9, 3).
 

Тогда можно было бы сказать, что человек, A, неправильно прочитал, если A увидел что-то в позиции, и не неправильно прочитал какую-либо другую позицию:

 misread(Person, Digit, Position) :- 
  saw(Person, Digit, Position),
  not(misread(Person, _, not(Position))).
 

И тогда правильной цифрой будет та, которая не будет неправильно прочитана:

 correct(Digit, Position) :-
  not(misread(_, Digit, Position)).
 

и, таким образом, решение может быть прочитано с: correct(X, Y).

Однако мне трудно понять, как я мог бы добавить ограничение, чтобы все неправильно поняли именно одну проблему. Любые подсказки по этому вопросу будут оценены.

Весь код вместе:

 saw(alice, 1, 0).
saw(alice, 0, 1).
saw(alice, 0, 2).
saw(alice, 6, 3).

saw(bob, 1, 0).
saw(bob, 0, 1).
saw(bob, 1, 2).
saw(bob, 6, 3).

saw(dan, 1, 0).
saw(dan, 0, 1).
saw(dan, 2, 2).
saw(dan, 9, 3).

misread(Person, Digit, Position) :-
  saw(Person, Digit, Position),
  not(misread(Person, _, not(Position))).

correct(Digit, Position) :-
  not(misread(_, Digit, Position)).
 

То, как я бы справился с этим:

 saw(alice, 1, 0, 0, 6).
saw(bob, 1, 0, 1, 6).
saw(dan, 1, 0, 2, 9).
 

Сначала констатируем факты. Тогда я бы закодировал тот факт, что только один неверно прочитан:

 chk(P, A, B, C, D) :- (saw(P, X, B, C, D), X = A);
                      (saw(P, A, X, C, D), X = B);
                      (saw(P, A, B, X, D), X = C);
                      (saw(P, A, B, C, X), X = D).
 

Это .. несколько жесткое кодирование «one is wrong». Я уверен, что это можно улучшить. Наконец, решение, указывающее, что существует 4 цифры, и применяющее к ним вышеуказанную «проверку»:

 digit(A) :- member(A, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]).

solve(A,B,C,D) :-
    digit(A),
    digit(B),
    digit(C),
    digit(D),
    chk(alice, A, B, C, D),
    chk(bob, A, B, C, D),
    chk(dan, A, B, C, D).

 

Итак, я нашел ответ на проблему, и теперь он есть в CodeReview:

 %- Read person saw number at position.
saw(alice, 1, 0).
saw(alice, 0, 1).
saw(alice, 0, 2).
saw(alice, 6, 3).

saw(bob, 1, 0).
saw(bob, 0, 1).
saw(bob, 1, 2).
saw(bob, 6, 3).

saw(dan, 1, 0).
saw(dan, 0, 1).
saw(dan, 2, 2).
saw(dan, 9, 3).

%- Consider the case when two people see one number and one person saw a anoth-
% er number. This doesnt actually mean the person "definitely" misread the nu-
% mber, but if the problem can be solved it measns they definitely did.
definitely_misread(Person, Digit, Position) :-
  saw(Person, Digit, Position),
  saw(Q, D, Position), Q == Person, D == Digit,
  saw(R, D, Position), R == Q, R == Person.

%- Read a person misread the digit at poisition at position.
misread(Person, Digit, Position) :-
  saw(Person, Digit, Position),
  not((definitely_misread(Person, D, P), D == Digit, P == Position)),
  (saw(Q, D1, Position), Q == Person, D1 == Digit),
  (saw(R, D2, Position), R == Q, R == Person, D2 == Digit).

%- Resolve if the question is actually the correct digit at that position.
correct(Digit, Position) :-
  (saw(alice, Digit, Position), not(misread(alice, Digit, Position)));
  (saw(bob, Digit, Position), not(misread(bob, Digit, Position)));
  (saw(dan, Digit, Position), not(misread(dan, Digit, Position))).
 

Ключевыми моментами являются:

1. Наложите дополнительные ограничения на misread (связанные с удаленным ответом, убедитесь, что другие люди не равны misread компоненту.
2. Включите a definitely_misread для повышения эффективности (к сожалению, без этого вы получите ошибку стека).

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

неверное прочтение / 3 безнадежно сложно. Сделайте это конкретным, выразив то, что другие люди читали:

 misread(Person, Digit, Position) :-
  saw(Person, Digit, Position),
  saw(Q, D, Position), Q==Person, D==Digit,
  saw(R, D, Position), R==Q, R==Person.
 

Примечание: непроверенный, я не могу сказать, поможет ли это решить головоломку.
Но следует выразить ограничение, просто соблюдайте порядок целей. Отрицание из-за сбоя — то, что мы имеем в обычном Прологе, — не может работать без конкретных данных для сравнения, затем saw/3 на Q и R (мы знаем, что у нас есть только 3 объекта) передают последующее отрицание. Действительно == означает not(A==B) — или в современном синтаксисе, \ (A==B) .

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

Поскольку пространство поиска настолько мало, неэффективное кодирование может:

 misread(Person, Digit, Position) :-
  saw(Person, Digit, Position),
  saw(Q, D, Position),
  saw(R, D, Position),
  maplist(==, [Q,D,R,R],[Person,Digit,Q,Person]).
 

Помещая все фильтры в конец, это приводит (плохо) к значению мощности пилы O ^ 3.

Переключение на dif/2 сделало бы порядок целей неактуальным и помогло бы решить проблему производительности. Например:

 misread(Person, Digit, Position) :-
  maplist(dif, [Q,D,R,R], [Person,Digit,Q,Person]),
  saw(Person, Digit, Position),
  saw(Q, D, Position),
  saw(R, D, Position).
 

PS: Я восстановил этот ответ (просто подсказка) после просмотра исходного ответа OP.