Problem trying to define exists precisely one in Prolog

Question

I am getting into Prolog and heard it is pretty good for solving logical puzzles. I found a bunch of (easy, in fact, easier to solve by hand than use Prolog) logical puzzles like the one described here. To restate:

A messy kid wrote a multiplication problem.

1. Alice saw 100 x 6.
2. Bob saw 101 x 6.
3. Dan saw 102 x 9.

Each one only misread digit. What is the real solution to the problem?

My first thought was to define a relation, "Person saw digit 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).

Then one could say a person, A, misread if A saw something at the position, and didn't misread any other position:

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

And then a correct digit would be one that is not misread:

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

and thus the solution could be read off with: correct(X, Y).

However, I am having difficulty understanding how I could add the restraint that everyone misread precisely one problem. Any hints on the matter would be appreciated.

---

All the code combined:

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)).

Answer 1

misread/3 is hopeless complicated. Make it concrete, expressing what other persons did read:

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

Note: untested, I cannot say if this will help to solve the puzzle. But should express the constraint, just observe the goals order. Negation by failure - what we have in plain Prolog - cannot work without concrete data to compare, then saw/3 on Q and R (we know we have only 3 entities) feed the subsequent negation. Indeed \== means not(A==B) - or in modern syntax, \\+(A==B).

Maybe try to visualize the dataflow as an SQL plan, you're instructing the join ordering.

Since the search space is so small, an inefficient coding could do:

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]).

Putting all filters at the end, this performs (badly) O^3 on saw cardinality.

Switching to dif/2 would make the goals order irrelevant, and would help for the performance problem. For instance:

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: I undeleted this answer (just an hint) after seen OP's original answer.

Answer 2

The way I'd tackle this:

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

First stating the facts. Then I'd encode the fact that only one is misread:

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).

This is .. somewhat hard-coding the "one is wrong". I'm sure this can be improved. Finally the solution, stating that there are 4 digits and applying above "check" on them:

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).

Answer 3

So I came up with an answer to the problem, and now have it on 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))).

The key points are:

1. Put further restrictions on misread (related to the now deleted answer, make sure that other people don't equal the misread component.
2. Incorporate a definitely_misread for efficiency (unfortunately, without it you would get a stack error).

Unfortunately, this makes it exceptionally verbose, which is why I have also asked a question on CodeReview.