An explanation of knight/knave/spy puzzles, with a complete list of valid puzzles of the form.

Context

Knight/Knave/Spy puzzles were popularized by Raymond Smullyan, they're a variant of liar/truthteller puzzles: http://en.wikipedia.org/wiki/Knights_and_knaves

Assumptions:

  • Knights always tell the truth
  • Knaves always lie
  • Spies can either lie or tell the truth
The most common form of the puzzles includes three people, A,B, and C. One of them is a knight, one is a knave, and one is a spy, but you don't know which is which. They all know each other's identities.

For example:

  • A says: I am a knight
  • B says: That is true.
  • C says: I am the spy!

Neither B nor C can be the knight. C can't because he claims to be the spy, and B can't because he claims someone else is the knight. Therefore A is the knight. B is saying something true, so he must be the spy, making C the knave.

  • A says: B is the spy!
  • B says: No, C is the spy!
  • C says: No, B is definitely the spy.

In this case, B can't be the spy because then both a knight and a knave would be accusing him of being the spy. And if B isn't the spy, then neither A or C can be knights since they wouldn't be telling the truth. Therefore, B is a knight, making C the spy and A the knave.

Types of Puzzles

There are only six possible combinations of knight, knave, and spy you can have for a particular puzzle:

  • Knight Knave Spy, Knight Spy Knave, Knave Spy Knight, Knave Knight Spy, Spy Knight Knave, Spy Knave Knight

Any statement made by someone in a puzzle can be classified according to what possibilities it eliminates. For example, the statement, "I am a spy", leaves the following possibilities, since the statement can only be made by a knave or a spy:

  • Knave Spy Knight, Knave Knight Spy, Spy Knight Knave, Spy Knave Knight

A spy can make any statement, (assuming spies aren't subject to paradoxes such as "this statement is false" or "saying that I am a knight would have the same truth value as this statement". I assume a spy is an ordinary person able to say anything), so it will always be a possibility that the speaker is a spy, leaving four combinations which may or may not be possible with a given statement. This leaves 2^4 or 16 different unique statements possible, based upon which of the 4 permutations of roles that statement eliminates.

For the following list, arrangements are represented in the following form: TFS means True False Spy, meaning A would be a knight, B would be a knave, and C would be the spy. For each of the following the order is based on the assumption that A is making the statement.

List of All Possible Statements

Statements are placed alongside their complements (e.g., "I am a knight" and "I am not a knight" are placed together, since each statement has the complementary sets of possibilities). Hence, if you ask a question of the form "Are you a knight?" you are guaranteed one of the two responses and resulting sets of possibilities.

Whenever possible statements are also arranged next to an equivalent form where the question is being asked about B rather than C, for example "B is a knight" vs "C is a knight", in which the possibilities for B and C are simply flipped.

For all of the following it is assumed that A is the speaker, the statements can be re-assigned to another speaker by changing the references to B/C accordingly and rearranging the values in the set of possibilities.

The Useless Statement: I am a knight

"I am a knight" or "I am not a knave". Any role can make that statement, so it eliminates no possibilities of arrangements of knights knaves and spies.

Possible arrangements: TFS, TSF, FTS, FST, SFT, STF

The Paradox: I am not a knight

Similarly, "I am a knave." This statement means that A must be a spy, since neither a knight nor a knave could make that statement.

Possible arrangements: SFT, STF 

The "True" Statement: I am not a spy

Included in this category is any statement which could not be said by a knave, such as water is wet, etc.

Possible arrangements: TFS, TSF, SFT, STF

The "False" Statement: I am a spy

This is a statement which could not be said by a knight, such as water is not wet, etc.

Possible arrangements:  FTS, FST, SFT, STF

B is a knave

This statement eliminates the possibility of Knight, Spy, Knave.

Possible arrangements: TFS, FTS, FST, SFT, STF 

B is not a knave

This statement eliminates the possibility of the speaker being a knave, and B being a knave if the speaker is a knight.

Possible arrangements: TSF, SFT, STF 

C is a knave

This statement eliminates the possibility of Knight, Knave, Spy

Possible arrangements: TSF, FTS, FST, SFT, STF 

C is not a knave

This statement means the speaker is either a spy or the only combination is Knight Knave Spy

Possible arrangements: TFS, SFT, STF 

B is a knight

This statement means the speaker is either a spy or the only combination is Knave Spy Knight

Possible arrangements: FST, SFT, STF 

B is not a knight

This statement eliminates the possibility of Knave, Spy, Knight

Possible arrangements: TFS, TSF, FTS, SFT, STF 

C is a knight

This statement means the speaker is either a spy or the only combination is Knave Knight Spy

Possible arrangements: FTS, SFT, STF 

C is not a knight

This statement eliminates the possibility of Knave, Knight, Spy.

Possible arrangements: TFS, TSF, FST, SFT, STF 

B is a spy (or C is not a spy)

This statement means you can't have Knight Knave Spy or a Knave Spy Knight.

Possible arrangements: TSF, FTS, SFT, STF 

B is not a spy (or C is a spy)

This statement means you can't have Knight Spy Knave or a Knave Knight Spy

Possible arrangements: TFS, FST, SFT, STF 

Recap

The above statements covers every possible arrangement except two, where you have TSF FST or TFS FTS left over. Both of these statements guarantee that someone is not the spy, regardless of who says them.

The last two statements have the property that knights/knaves give identical answer to the question posed, and the statement reveals something about another role without revealing anything about the speaker.

If you asked me, I would say that B is the spy (or "if you asked, I would say C is not the spy")

This statement means that C is not the spy.

Possible Arrangements: TSF, FST, SFT, STF

If you asked me, I would say that B is not the spy (or "if you asked, i would say C is the spy")

This statement means that B is not the spy.

Possible Arrangements: TFS, FTS, SFT, STF

If a Spy says the first statement, C can not be the spy since A is the spy. If a knight says the first statement, C can not be the spy since B would have to be the spy. And if a knave says the statement, it means he's telling you what he would say if you asked, meaning he's lying about the lie he'd tell, meaning he's telling the truth, so B would be the spy in that case.

Basically, it uses a double negative to get around the fact that a knave normally lies. "If and only if this statement is false, B is the spy" would also work, but basically there's no real way to accomplish one of these statements without self-reference or a "B would say" type statement.

It is interesting to note that claiming B is the spy is equivalent to claiming C is not in terms of its implications, whether stated normally or in the "if you asked" form. This is interesting because although the two are logically equivalent from the point of view of someone approaching the problem, that sort of behavior isn't guaranteed, saying "I am the spy" is not equivalent to saying "B is not the spy", for example. It's just that knights and knaves are guaranteed to make opposite claims about the two other people as to whether they're the spy.

The nice thing about this whole setup is that, covering the last two cases, any statement whatsoever is reducible to one of the above forms based on the permutations it eliminates.

Possibilities

Since we have 16 possible statements and three people to make them, we have 4096 possible puzzles. A lot of those are reducible. Not counting the 16 ones where everyone says the same thing, you have two-way symmetry in 720 of them, and three way symmetry in 3360 of them. Which reduces to 560 +240+ 16= 816 unique puzzles when you discount rearrangements.

After running a program to generate the entire set of puzzles and test for solutions, out of that total of 816, 381 puzzles have no unique solution, and 161 puzzles have no solution at all, where the problem equates to a paradox. 274 puzzles have a unique solution, qualifying as valid forms of the puzzle.

This may not count as a minimal form for variants of the puzzle. There are some cases where A and B say the same thing, in which C can make a statement about A or B and it reduces to the same puzzle. Accounting for symmetry, there are 16 things those two people can say, and 12 things the third person can say which ends up being equivalent. Subtracting the 12 possibilities where they all say the same thing, that leaves 180 possibilities, half of which (90) could be eliminated, leaving 726 total.

Puzzles with no unique solution

Puzzles with no solution

Puzzles with one unique solution (i.e. valid puzzles)

Fun questions

1. In just three questions, determine who the knight knave and spy is. No matter what they answer, you should be able to figure out who is who in three questions. You can choose and direct your questions dynamically.

2. In just two questions, figure out who the spy is. Your questions can take any form, and can be chosen and directed depending upon what answers you receive.

3. For this and the next problem, assume we're working with a question set that doesn't include the last two statements, of the form "what would you say if". With this restriction, is it still possible to always solve the puzzle in just three questions? What is the minimum number of questions to identify the spy, and to identify each person?

4. You're a knight, and your friend the knave is being interviewed with you and a spy to find out who is who. The spy makes some incidental statement, such as "I am not a spy." Can you and the knave with one statement each make your identities clear? Can you do this for any possible statement of the spy?

5. Let's say that instead of just dealing with three people, you have to find out who the knights, knaves, and spies are out of an arbitrary number of people. One thing you can observe about this type of problem is that if you have a majority of spies it will be impossible to solve. For example, with 100 possible candidates and 51 spies, you have no way of getting at the truth of anything. However, if you know that there are 49 spies or less, you can determine who is who.

Let's say you're dealing with a large number of people, on the order of a thousand or so, and you need to identify all the spies from that group. You know that the spies are a minority of all the people there. Find a fast and effective method for identifying whether each person is a spy or not, without asking too many questions.

It should take less than 5*(the number of people) questions. (linear time, in other words)

(That last problem has been tackled by a mathematician, Dr Mark Wildon of Swansea University, who's managed to prove an optimal solution: http://www-maths.swan.ac.uk/staff/mjw/knights.html

 

email me

End Notes

There aren't very many interesting puzzles where only one or two people speak, and technically those puzzles are a subset of the puzzles where all three people speak anyway, since you can just take all the puzzles where A says "I am a knight" and construct a two-person puzzle out of the remaining answers, since A's statement reveals no informaiton.

You could have some puzzles where two or more people make multiple statements, with a practical limit of 6 statements, since if any individual statement doesn't eliminate any of the possibilities it could just be removed from the puzzle. (statements about statements, such as "B is lying" and "C is telling the truth", should still be able to considered under the same system, since it would be equivalent to claiming the opposite or the same thing)

In a puzzle with four or more people with varying combinations of liars and truthtellers, the range of possible statements grows more complex, since you can start talking about pairs of people and so on, in general there should only be 2^N statements, where N is the number of possible configurations for that type of puzzle.