"Five hats" logic puzzle with strange solution in _Prolog By Example_


#1

I’m reading “problem 72” from this book Prolog by Example, which takes a rather distinctive approach to solving a little logic puzzle. The problem is and solution are on the first two pages of this PDF. The problem looks like this:

There are five hats. Three of them are white and two are black. Three men are standing one behind the other, i.e. the second sees the first, the third sees the first, and the third sees the second. Each has one hat on his head. Only two hats are black, so it is impossible that each man has a black hat. The third says that he does not know what hat he has on his head. Then the second says the same. So neither the third, nor the second knows what hat he has himself. The question is what hat the first man has.

The solution in the book is:

:- op(100,xf ,holds).
:- op(150,xfy, .).
:- op(200,xfx, if).
:- op(220,xfy,and_).
:- op(300,xfx,can_verify).
:- op(300,xfx,sees).
:- op(300,xfx,is_deducible_from).
:- op(300, fx,it_is_deducible_that).
:- op(300,xf ,is_false).
:- op(320,xfy,and).
:- op(340, xfx, knows_that).
:- op(340,xf ,knows_what_hat_he_has_himself).
:- op(360,xfx,has).
:- op(380, fx,the).
:- op(380,xf ,hat).

X holds:- fact(X).
X holds:- fact(X if Y), Y holds.
X and_ Y holds:- X holds, Y holds.

fact(X):- ( the_problem_is_stated_as(Text) ;
              inference_rules_are_stated_as(Text) ),
           member(X, Text).

question(X):- it_is_deducible_that X holds, output(X).

the_problem_is_stated_as(
there_are_five_hats. three_of_them_are_white_two_are_black.
three_men_are_standing_one_behind_the_other_i.e. the second sees
the first. the third sees the second. the third sees the first.
each_has_one_hat_on_his_head. ie_the_statement. the third has
black hat and the second has black hat and the first has black
hat is_false.
  the_third_said_that_he_does_not_know_what_hat _he_has_on_his_head.
then_the_second_said_the_same. it_means_that. the third
knows_what_hat_he_has_himself is_false. and_similarly. the second
knows_what_hat_he_has_himself is_false.
the_question_is_what_hat _the_first_man_has).

inference_rules_are_stated_as(
it_is_deducible_that A_man has white hat if Statement is_false
and_ Statement is_deducible_from A_man has black hat. similarly.
A_man has white hat is_deducible_from An_assumption if Statement
is_false and_Statement is_deducible_from A_man has black hat and
An_assumption.
  A_man knows_what_hat_he_has_himself is_deducible_from An_assumption
if A_man can_verify An_assumption and_
A_man has
Certain hat is_deducible_from An_assumption.
  Man1 can_verify Man2 has Some hat if Man1 sees Man2. A_man can_verify
Fact1 and Fact2 if A_man can_verify Fact1 and_ A_man
can_verify Fact.
  Everything is_deducible_from An_assumption if An_assumption
is_false.
  and_it_is_all_for_solving_the_problem).

I’ve also OCR’d the code into this gist if that’s easier for you to read/work with.

I see a lot of problems with this code, and I’ve tried to massage a separate copy of it into working order but I keep getting stuck. I suspect this is old code and only ran on a particular implementation from yesteryear, and it’s not mentioned in the text what it would be.

  • Trying to redefine the operator for . seems like a very dangerous idea
  • I don’t see how member/2 could ever have produced “items” from the text of these predicates, even if the . operator had its traditional role as “cons”
  • The the and hat operators have the same precedence level, which is illegal in SWI and I don’t see how that could have worked ever
  • There are a lot of “nearby” atoms that are not declared operators yet stand alongside each other in a way that seems unlikely to work to me

There are some really bad ideas in here (operator and alongside operator and_ comes to mind). That said, there are also a few clever ideas here that I like, especially X holds :- fact(X if Y), Y holds.

I don’t think writing the program in this really idiosyncratic way is helping the readability or comprehensibility much, but I’d still like to see this with the bitrot fixed, or at least understand what was different about Prolog back when this worked. If anyone has a chance to take a look I would appreciate it!


#2

Interesting solution, though only for illustrating that Prolog really is just Logic. Steps to modernize:

  1. Replace those . with , and make a list out of them.
  2. One item per line, and blank lines for spacing out the logic.
  3. Use % to comment all those items that are not being used., such as there_are_five_hats. And get rid of underscores therein.
  4. Maybe get rid of and_, and use parentheses where English would make this implicit.
  5. After illustrating the solution I would further clean that up by getting rid of cruft. ‘the’ has no functional purpose here, for example. Prolog sees (the second) as a term and matches that term.