The Hardest Logic Puzzle Ever - History

History

Boolos credits the logician Raymond Smullyan as the originator of the puzzle and John McCarthy with adding the difficulty of not knowing what da and ja mean. Related puzzles can be found throughout Smullyan's writings, e.g. in What is the Name of This Book?, pp. 149–156, he describes a Haitian island where half the inhabitants are zombies (who always lie) and half are humans (who always tell the truth) and explains that "the situation is enormously complicated by the fact that although all the natives understand English perfectly, an ancient taboo of the island forbids them ever to use non-native words in their speech. Hence whenever you ask them a yes-no question, they reply Bal or Da—one of which means yes and the other no. The trouble is that we do not know which of Bal or Da means yes and which means no". There are other related puzzles in The Riddle of Sheherazade.

The puzzle is based on Knights and Knaves puzzles. One setting for this puzzle is a fictional island inhabited only by knights and knaves, where knights always tell the truth and knaves always lie. A visitor to the island who must ask a number of yes/no questions in order to discover what he needs to know). A version of these puzzles was popularized by a scene in the 1986 fantasy film Labyrinth. There are two doors with two guards. One guard lies and one guard does not. One door leads to the castle and the other leads to 'certain death'. The puzzle is to find out which door leads to the castle by asking one of the guards one question. In the movie, the protagonist, named Sarah, does this by asking, "Would he tell me that this door leads to the castle?"