Knights and Knaves

A Knights and Knaves puzzle, also called Liars and Truthtellers, is a type of deduction logic puzzle where solvers are presented with a set of people who either always tell the truth or always lie, and solvers have to determine which are which. Commonly used as a way of teaching Boolean logic, these puzzles have existed formally since at least the 1930s, and have had several variations in name, goal, and exact nature of the people involved.

Most K&K puzzles involve either identifying which people are knights/knaves, figuring out the answer to a particular question, or both (if doing the former is required to accomplish the latter). The most famous example is of two guards standing at a split in a road, where one path is safe to travel on. Between the two guards, one always lies, and one always tells the truth, and together they will only answer one question. The goal is then to both figure out who is who, and which road is safe, based on the answer to a single question.

Background

The earliest (currently) known version of this puzzle is from 1931, written by the philosopher Henry Nelson Goodman. In his version, 'nobles' always tell the truth, and 'hunters' always lie, and the question posed involved three people (either nobles or hunters) being asked about who they are.

In 1953, Maurice Kraitchik presented a similar puzzle in his book Mathematical Recreations, instead replacing 'nobles' and 'hunters' with a fictional pair of races known as 'Arbus' and 'Bosnins'. A new setting of a deserted island was added, but the question posed by Goodman remained almost unchanged.

The most common name for this puzzle type, 'Knights and Knaves', comes from 1978 in Raymond Smullyan's 'What is the Name of this Book?', which collected various types of logic and deduction puzzles. Smullyan's version retains the deserted island aspect of Kraitchik's problem, but once again changes the inhabitants to be entirely 'Knights' and 'Knaves'. In the book, he presents 13 problems relating to questions asked to some residents, but then adds in another type of person: 'Normal'. Normal people are not bound by the rules of knights and knaves, allowing them to lie and tell the truth whenever they want. Lastly, Smullyan also added some additional constraints in a final set, regarding marriage between island residents. He made it so that knaves could only marry knights and vice versa, leaving normals to only marry normals. This allowed for a series of puzzles regarding unknown couples to be written.

The Two Roads

One other variation on the puzzle was written in between the 1931 and 1953 versions. In it, two guards stood in front of a fork in a road, with a sign explaining that one of the two only lied, and one was always truthful. In addition, travellers could ask only one question of the two guards. The problem with this is that direct questions about the safety of the roads will only be answered truthfully 50% of the time. One possible solution to this puzzle is to ask the following question:

An XKCD comic making fun of the Knights and Knaves puzzle.

What would the other guard say if I asked him which road is the safe road?

In this case, no matter which guard is asked, the answer will be the unsafe road. Suppose the truthful guard was asked. He knows the other guard lies, and if you were to ask the lying guard which road is safe, he would point to the unsafe one. Therefore, the truthful guard will relay that same response to you. Alternatively, if you asked the lying guard, they know the other guard tells the truth, and would point you in the correct direction. Since this guard always lies, he would switch this response when relaying it, and tell you the unsafe road is safe. With this, you can always use this question to identify the unsafe road (and by process of elimination, the safe road too).

This version of the Knights and Knaves puzzle was famously used in the movie Labyrinth.

Puzzle Application

Goals

There are a few possible goals in a K&K puzzle. In most traditional puzzles, the goal is simply to determine the identity of those involved. Others will require you to answer a particular question, or propose useful questions to get certain information.

Hunt puzzle versions of a K&K puzzle may have similar goals, but will almost always have a way to extract from that goal. An identification-based puzzle may focus on the binary (or ternary) nature of the peoples' statuses, or look at the names or other known information about each person to be used in combination with their status. A puzzle where determining other qualities about each person through their statements allow for more open extraction methods. Statements can theoretically be about anything (position in a sequence, age, anything that you might see in a zebra puzzle, etc.), so the extraction methods available to the writer are mostly just limited to what they can apply to the resulting information set. The 'Two Roads' variation, as well as any puzzle where the goal is to formulate an appropriate question to ask the people involved, is not easily implemented as a hunt puzzle, due to the difficulty in automatically parsing answers to open-ending questions, and the difficulty in going from such an answer to a single word/phrase puzzle answer.

Complications

Since this puzzle has had time to evolve, there are of course many possible twists and complications that can be added to a given situation to add more difficulty. These include:

• Alternators - People who alternate between lying and telling the truth, statement to statement. The difficulty is in both determining who must be an alternator, as well as determining which alternation they're on with any given statement.
• Normals - As mentioned in Smullyan's book, they're people who can lie or tell the truth at will. The difficulty comes less in determining whether they're a normal or not (although that may still be difficult), but in determining whether their individual statement are truthful or lies.
• Mutes - People who cannot make statements, but can have statements made about them. The difficulty here is in determining someone's state based entirely off of second-hand information, as well as differentiating between quiet truthtellers and liars.
• Delusional - People who only believe false facts, meaning that any truthful/liar status is affected by what they believe rather than what is actually true. Obviously, this is difficult because
  • Partials - The 'alternator' equivalent for delusional/nondelusional people.
• Alien Language - The language spoken by the people in the puzzle is unknown, apart from knowing possible translations for a few words (like Yes/No), but not what translation go with which word. This is the basis for Boolos' 'Hardest Logic Puzzle Ever'.

As a whole, puzzles that involve people with any of these statuses should explicitly note that they're an option to pick from. Since these are not the default for Knights and Knaves puzzles, including any complications without acknowledging their presence makes the puzzle unfair to solvers, as they cannot be expected to know of them, nor assume their presence.

Strategy

Identification of a Knights and Knaves puzzle is easy compared to general Truths and Lies puzzles, as there's usually more setup involved in a K&K puzzle. In addition, people making statements usually implies a K&K is being solved, even without explicit instructions.

When approaching a K&K puzzle to solve, the first thing to look out for among the statements is paradoxes. For example, in a basic puzzle, nobody can claim to be a liar, since a truthteller doing so would be lying, and a liar doing so would be telling the truth.

Another useful tactic is to pretend either that everyone is lying or that everyone is telling the truth, and seeing where things start to fall apart. While it's almost certain that these will not result in a valid state, they can give solvers an idea of which people should be given a closer look.

TO DO

Notable Examples

Played Straight

• Paranoia (MITMH 2003) (web) - A relatively straightforward liars and truthtellers. Involves taking three statements from each person and ordering them based on them.

Notable Twists

• The Sexaholics of Truthteller Planet (MITMH 2009) (web) - A Knights and Knaves puzzle, but with the ability for each to switch to the other overnight due to a mysterious disease passing through the planet. Solvers have to determine who is infected, and track the changes in truthfulness each day.
• Murder at the Asylum (MITMH 2018) (web) - Has the traditional truthtellers and liars, but adds an additional 'alternator', who will lie and tell the truth with alternating statements. In addition, each person is assigned a status in the murder (innocent, accomplice, or murderer), and a sanity (sane, delusional, and partial), the latter of which affects what people believe are true, rather than how they make their statements. In the end, solvers need to determine the status of all the residents in all three categories.

See Also

• List of Knights and Knaves puzzles
• Raymond Smullyan's What is the Name of this Book (See Page 20 for K&K puzzles)