The famous two-guard puzzle is a staple in role-playing games and the fantasy genre. It has provided an interesting logical challenge to players of all ages and often adds a nice interactive aspect to dungeon puzzling.
These puzzles come from the class of Knights and Knaves logic problems.
This post describes the standard two-doors puzzle, explains its solution, and then discusses several extensions which can be easily adapted to fit into any campaign or setting.
Standard Two-Doors Puzzle
Before you are two doors, each with a guard. One guard is honest and always tells the truth. The other is dishonest and always lies. One door leads to salvation and the other to a grizzly death; you must identify which is which but can only pose one question to one guard. What do you ask to guarantee a correct choice?
This is the standard from for the two-doors puzzle. Its structure is simple - ask a question and receive an answer - but its premise is delightfully simple; how can you know whether or not you are being lied to?
Whenever a question is asked to a guard, the guard takes the statement, determines its solution, and then either responds with the answer if they are honest or reverses it if they are dishonest. The difficulty lies in offering a statement that produces an answer that only depends on the nature of the two doors - not on the nature of the guards.
Simply asking 'Is this the right door?' is clearly incorrect. The liar and truth-teller will certainly give conflicting answers.
We will examine the solution using truth tables. These encode the truth of several statements given all combinations of the door / guard assignments. Without loss of generality, we will refer to guard A as an arbitrarily selected first guard and guard B as the second, other guard.
The first two rows of the table above define the four possible guard and door assignments. The next two show the result of asking 'is door A the correct door?' and 'does the other guard lie?' to the first guard.
How was it that the second question gave us a tautology? It stems from the inversion of asking the question to a liar or to an honest guard. This highlights the difficulty of the problem.
Let us establish some notation definitions:
The solution to the problem is to leverage a referential property. We ask the guard what the other guard's response is, thereby obtaining a nicely-formed solution.
Would the other guard tell me this is the correct door?
We see that the sentence produces the negation of our desired goal, independently of what the guard assignment is! We thus ask this question to any guard, and if they say yes we know to pick the opposite door, and vice-versa.
An Unreliable Guard
Now for a more complicated setup:
You have two doors and one guard. The guard sometimes lies and sometimes tells the truth.
The case of the unreliable guard is a bit trickier. How can it be handled?
In the previous problem we were able to obtain a solution independently of what the guard's truth-assignment was. We simply asked the guard what the other guard would have said and in so doing guaranteed we would get exactly one negation.
In this problem we can take advantage of a similar trick, namely that two truths make a truth and two lies make a truth as well. If we pass a question with such stacking we can cancel out any truth-assignment effects and solve it with one question:
Would you tell me this is the right door if I asked you?
This answer also holds for the first problem, and in my opinion is easier to follow. We don't even have to worry about picking the opposite door. If the guard says 'yes' we just go with that door.
Note that we dropped the superscripts for the guard as there is only one.
Lost in Translation
You have two doors and one guard who always tells the truth, only this guard can only speak in a foreign language where they use 'Da' and 'Ja' instead of yes and no. Unfortunately, we don't know which word corresponds to yes and which to no.
Can we still identify the correct door in one question?
Clearly we want to pose a question that remains invariant to the nature of the translation. We need to find a question that will produces 'Ja' if the door is correct and 'Da' if the door is incorrect, irrespective of what Da and Ja really mean.
Would you respond `Ja' if door A were the correct door?
As we can see, we get Ja if it is the correct door and Da otherwise. This used the translation of the language as a filter is a similar manner as with truth earlier. The filter successfully converts our target question into an easily interpreted result.
Note that the E above is the translation function that maps a truth value into Da or Ja.
Three Gods Puzzle
This puzzle, known as the Hardest Logic Puzzle Ever on wikipedia, is merely an extension of the logic puzzles above.
There are three gods. One always tells the truth, one always lies, and the third sometimes tells the truth and sometimes lies. The gods only answer yes or no questions, but do so in their own language with 'Da' and 'Ja.' You do not know which means yes and which means no. You must correctly identify the three gods by posing no more than three questions, each put to a single god.
Well, that is certainly more complicated than what we had before. Let us begin by defining the space of combinations. There are three gods, Lier, Honest, and Random, which are arbitrarily assigned. There is also the translation for Da and Ja. This produces twelve total combinations.
- The gods only answer yes/no questions. The asker of a non-yes/no question is punished.
- The asker of a yes/no question that cannot be answered (ie, a paradox) is also punished.
- Whenever Random is given a question, it `flips a coin' in its head to determine whether to act as Lier or Honest.
- One can ask questions to the same god multiple times, but only three questions total split as you desire.
We make use of the tricks from the previous questions to remove the bias of false-hood, and use it to determine whether the first god is Random or not.
Unfortunately, the final answer is scambled due to the language translation. The trick is to pass it through a second 'filter' to get what we are truly after.
'Would you respond 'Ja' if I asked you if you were Random?
Thus we see that we can force a Ja if the first god is Random.
The rest of the problem is solved in a similar manner. If god A is random, our second question is to god B:
@god B: 'Would you respond 'Ja' if I asked you if you are honest?'
Again, a Ja means that god B is honest. Thus the puzzle is solved; god C has the remaining state.
If god A is not random we need to ask two questions:
@god A: 'Would you respond 'Ja' if I asked you if you were honest?' @god B: 'Would you respond 'Ja' if I asked you if you are Random?'
and thus the problem is solved in all cases with at most three questions.
More Difficult Three Gods Puzzle
The 'exploding heads' gods puzzle is even more difficult. Here you lift the restriction that gods punish questions involving paradoxes. In this problem they simply do not answer instead (or their heads explode), giving a third way to gain information. I will not go through it here, but the question and its solution is on wikipedia.
Some Notes for DMs
These puzzles can be quite difficult, especially the three-gods version. Not all of these are suited for live play. If you do run it, I recommend presenting the problem towards the end of a play session and let them noodle it out on their own time. That is, of course, if you trust them not to look it up.
Other role-playing considerations:
- Players may avoid the puzzle by brute force; attacking the guards or just guessing a door and being prepared for the consequences is fine!
- It is often fun to continue interactions with the guards after the puzzle is completed. Dialog with a Lier or Random is entertaining.
- Doors don't have to be doors. It can be a choice between two treasure chests (one trapped, of course), pulling two levers, drinking one of two potions, stepping through one of two portals, etc.
- Guards don't have to be humanoid soldiers. They can be mystical psychic statues, sphinxes and other magical beasts, or even take on the form of visions that infect the character after the question is asked. You can also write questions on stones and toss them into a well, whisper questions into a seashell, or ask them to spirits and then read the answers from a set of Tarot cards.
- You can always give hints and/or let players roll for intelligence or wisdom to get past a puzzle that is significantly blocking progress. Another option is to make the puzzles optional, and to give XP if you solve it 'in real life'.
- It can be entertaining to place an entity in a game that is a Liar or Random without putting an explicit puzzle around it and let the players figure it out for themselves through interaction
That's all. Happy questing!
Not Registered Yet? No problem.
Do you want Strolenati super powers? Registering. That's how you get super powers! These are just a couple powers you receive with more to come as you participate.
- Upvote and give XP to encourage useful comments.
- Work on submissions in private or flag them for assistance.
- Earn XP and gain levels that give you more site abilities (super powers).
- You should register. All your friends are doing it!
? Responses (7)
Didn't read , don't have time ,REALLY looking forward to this on monday! I hope it lives up to my expectations!
I like this sub a lot, Mageek puzzle-master! Although I won't be using this personally cos I'm still a half-player in transition to becoming green player, I like how this clearly sets out the premise and then solutions to this type of logic puzzles.
4.5 out of 5 Look forward to more of this Oh puzzle master!
Well, this is very good! Excellent use of images. Academic tone in places, but still awesome. Not sure how you could avoid that considering the material.
You have carved out a unique niche, Mageek! Love the accompaniment of images. Bit stuffy reading in places as val mentions, but still so good!!
Speaking of submissions ready-made to be popped into an epub...
Entertaining and the work you put into it really shows.