The Hardest Logic Puzzle Ever

Or: The Prince from Turandot, Bilbo Baggins, Sarah Williams (from the movie Labyrinth), and the Dread Pirate Roberts are all very glad they weren't being questioned by Raymond Smullyan.


Today's post is about logic puzzles. Many people do not like them, and if you are reading this and you are such a person and are reading this, don't worry. I will soon have an upcoming post about beer, or art, or chilaquiles. Something more colorful. Something less sterile. Just wait. And hell, maybe I'll even be able to breathe some life into logic puzzles if you don't find them naturally interesting the way I do.


I was recently on a wikipedia article and saw a link to something called "The Hardest Logic Puzzle Ever". I'm not sure why I've never been told about this. I love puzzles. I love logic puzzles especially. I found the death last year of Martin Gardner to be a very sad thing. I tell people logic puzzles at parties (as you can imagine, I am the life of the party).


Boy is this one a doozy. At least I think so. Admittedly, I don't yet know the answer.


I'll start by just stating the problem. This statement of it was I believe Smullyan's own, original statement. It's taken from above wikipedia page

Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are da and ja, in some order. You do not know which word means which.

This may already look familiar to you. Especially if you've seen the movie Labyrinth. It's got David Bowie in it if you haven't, so maybe that'll make you want to see it, then it will look familiar. These seem to be known generally as "knight and knave" problems, problems where knights tell the truth and knaves lie, all of which have their roots in Smullyan. Even the one in Labyrinth, for which they say Smullyan was an inspiration directly. *


Raymond Smullyan is a logician and writer. He supposedly has a fantastic guide to Gödel's incompleteness theorem accessible to anyone fairly well versed in first-order logic that's on my reading list. He also apparently writes about piano, taoism, recreation mathematics, and magic. Seems like an interesting fella.


I have a particular love of logic puzzles that I may explore further in a post next week. I give out three generally, in order of least to most difficult, and give people a week to get them. On the Hardest Logic Puzzle Ever (after: HLPE) I am giving myself two weeks. I will post the answer then. Today I'm posting my three favorites, though. In a week I'll post more about logic puzzles in general, and the answers to those three. Plus I'll post any work I have on HLPE. The next week, I'll post the solution or solutions to HLPE and about it. (I know George Boolos wrote about the puzzle.)


Here are your puzzles:
1) Gnomes buried to their Gnecks


Of course Gnomes have Gnecks. Here's a hat-color problem.

I did not make this picture. Anyhow, here's the deal: These gnomes wake up buried to their gnecks. They are told that two of them are in blue hats, two in red hats. They're told if any one of them can guess his own hat color, then they all go free. Get it wrong? Death for all of them. They also know where each of the other gnomes are, and which way they are each facing (basically they know who can be seen by whom).  Whic, by the way, the one on the far right can see the two in front of him, the guy directly ahead of him can see the one in front of him. Obviously, no one can see past the wall. So these gnomes are totally logical and are pretty quick, so which gnome if any figures out his hat color?


2) Blue, Brown, Green eyes.


This is a similar sort to the last problem. It's been covered by the writer of XKCD. His write up gets around most of the bad questions I hear about it. To save space, I'm just linking to his. Here it is: http://xkcd.com/blue_eyes.html


Note, this is one of my favorites of all time. I find it fun, and I find it very rewarding.


3) Don't Get Stuck with Random


This feels like a slightly tamer version of HLPE and its solution might give us a clue, where its solution fails on HLPE, we may clearly see the obstacles presented by HLPE. It's a sort of Knights and Knaves problem. It's pretty difficult. Here we go. 


You enter a kingdom and are told you are to marry one of the three daughters of the king. The eldest always tells the truth. The middle daughter will randomly tell you the truth or lie to you.  The youngest will only ever lie to you. Despite being at different ages, it's impossible to tell which one is which. The king isn't telling you who's who. You don't get a full interview. You get to ask one yes/no question to any one daughter (but remember, you won't know which it is you will be talking to). Your goal is clear: you want a question that will lead you to safely select either the eldest or youngest, but not to select the middle daughter.


Well, there you are. My three favorite puzzles, and the puzzle I plan to struggle with. If you have an interest in this, watch for my post next week, when I'll reveal answers and further explore concepts. If you don't, I'll have more not-about-logic-puzzle posts soon.




*This one is fairly easy. You're at a fork in the road. One road leads to paradise, the other to certain death. There are two identical guards, you know one's a knight and the other a knave. Ask a single question to choose the correct road. That is, the one not to certain death.