Logic Puzzles – Efficient Solution for Knights and Knaves Puzzle

discrete mathematicslogicproof-writingpropositional-calculuspuzzle

I am working on a Knights and Knaves logic puzzle, and I have formulated a solution using a truth table. However, I'm wondering if there's a more efficient or faster way to arrive at the solution without having to manually create a large truth table, especially in cases with many statements.

The puzzle I'm working on involves five locals, A, B, C, D, and E, each making specific statements. The rules are as follows:

Knights always tell the truth.
Knaves always lie.
The statements from the locals are as follows:

A: "D is a knight, or E is a knave."

B: "Me and E are different."

C: "I am a knight or E is a knave."

D: "A is a knight or E is a knight."

E: "B is a knave or I am a knight."

My current solution involved creating a truth table with 32 combinations, but I'm looking for a more efficient approach to determine which locals are knights and which are knaves.

After my lengthy process, I concluded that everyone except E is a knight.

Is there a more efficient way to solve this puzzle without the need for a truth table? If so, I would appreciate any guidance or insights on how to approach such problems more effectively.

Best Answer

Whenever anyone in a knight-or-knave problem says a statement $P$, we can read it as the guaranteed to be true statement

"Either I am a knight and $P$ is true, or I am a knave and $P$ is false."

Usually, though this is guaranteed to be true, it is also more complicated. But this has a good chance of simplifying nicely when anyone makes a self-referential statement. In this case, B is saying "Me and E are different". We can fix the grammar error at the same time as we deduce the true statement

True version of B's statement: "Either I am a knight and E is different from me, or I am a knave and E is the same as me."

In other words, "Either I am a knight and E is a knave, or I am a knave and E is a knave". No matter what's up with B, we deduce that E is a knave!

This is the "break-in". Now that we know that E is a knave, the five statements simplify to:

  • A: "(true statement)."

  • B: "I am a knight."

  • C: "(true statement)."

  • D: "A is a knight."

  • E: "B is a knave."

A and C are both knights because they make true statements. D is a knight because D claims that A is a knight, which is true. Finally, since E's statement must be false, B must be a knight.

Here are some general tips that can help us arrive at this particular solution.

  1. Turn assertions made by people in the puzzle into statements that you know are true. Another way to think about the operation we began with is that whenever person A says statement P, this tells us "P xor (A is a knave)".
  2. Look for statements we can understand with a smaller truth table. When B says, "E is different from me", we can do just a 4-case truth table to analyze this statement completely: we just need to know whether B is a knight, and whether E is a knight. This is true to a lesser extent for everyone else: when A says "D is a knight or E is a knave", we need only an 8-case truth table to deal with A, D, and E. B and C are irrelevant.
  3. Look for break-in deductions. This is a tip that has to do with puzzle-solving, rather than logic in general. In a well-written puzzle, there should be some way to solve it that doesn't require brute force.
  4. When you've made progress, simplify. Once we deduce that E is a knave, everyone else's statements become simpler to analyze.
  5. If you must do casework, think about valuable cases to choose. An alternate solution path here is to realize that everyone's statements hinge on whether E is a knight or a knave. So if we consider the two cases "E is a knight" and "E is a knave", then in both cases we can simplify considerably. In one case, we solve the problem; in the other, we arrive at a contradiction.
Related Question