3 ms·
The article suggests using Boolean logic, so let's apply it: One way to solve this is to introduce a Boolean variable for each of A,...,G, and to use 1 to denot
by triska 3y ago
The article suggests using Boolean logic, so let's apply it: One way to solve this is to introduce a Boolean variable for each of A,...,G, and to use 1 to denote that a statement is true, and also to denote that the corresponding person tells the truth. It then remains to relate the truth of each statement to the truthfulness of the person making the statement.
In Prolog, we can express these relations with CLP(B), constraint logic programming over Boolean variables:
?- use_module(library(clpb)).
true.
?- sat(G),
sat(E),
sat(C =:= ~D),
sat(A =:= (B =:= (C =:= (D =:= (E =:= (F =:= ~G)))))),
sat(~A),
labeling([A,B,C,D,E,F,G]).
Yielding 4 solutions that satisfy all constraints:
G = 1, E = 1, C = 0, D = 1, A = 0, B = 0, F = 1
; G = 1, E = 1, C = 0, D = 1, A = 0, B = 1, F = 0
; G = 1, E = 1, C = 1, D = 0, A = 0, B = 0, F = 1
; G = 1, E = 1, C = 1, D = 0, A = 0, B = 1, F = 0.
From this, it is clear that there are 3 engineers, in all possible situations consistent with the description.
If we omit the labeling/1 goal which enumerates all solutions, then we get a symbolic representation of all remaining constraints:
G = 1, E = 1, A = 0, clpb:sat(C=:=D#B#F), clpb:sat(C=\=D).
From this, it is clear that there are at least 2 engineers in every solution: A (as stated in the description of the puzzle), and either C or D (but not both).
Tested with Scryer Prolog.
- carapace 3y agoYou're a treasure sir! The thing I find especially interesting about these sorts of puzzles is the translation from the word problem to the logical formalism. It seems like a separate domain from solving the problem itself.
- triska 3y agoWith Prolog, we can often very naturally map such puzzles to programs, or at least to declarative descriptions that can be easily interpreted by Prolog programs. For instance, in this concrete case, with a suitable operator definition for the operator says, we can write: :- op(800, xfy, says). solution([A,B,C,D,E,F,G]) :- G = salesman, E = salesman, C says D = engineer, A = engineer, A says B says C says D says E says F says G = engineer. It is then left to interpret the statements, which we can do for example with: :- use_module(library(dif)). engineer says Stmt :- false(Stmt). salesman says Stmt :- true(Stmt). false(A = B) :- dif(A, B). false(engineer says Stmt) :- true(Stmt). false(salesman says Stmt) :- false(Stmt). true(A = A). true(engineer says Stmt) :- false(Stmt). true(salesman says Stmt) :- true(Stmt). Yielding: ?- solution(S). S = [engineer,engineer,engineer,salesman,salesman,salesman,salesman] ; S = [engineer,salesman,engineer,salesman,salesman,engineer,salesman] ; S = [engineer,engineer,salesman,engineer,salesman,salesman,salesman] ; S = [engineer,salesman,salesman,engineer,salesman,engineer,salesman] ; false.
- _a_a_a_ 3y agoThat is most excellent, thank you