Solving Knights and Knaves with Alloy • Hillel Wayne (2023)

There’s a famous logic puzzle, originally from Raymond Smullyan, called a “Knights and Knaves” puzzle. We have a set of people, all of whom are either a Knight or a Knave. Knights only make true statements, and Knaves only make false statements. Usually the goal of the puzzle is to find out who is what. For example, if we have two people, A and B, and A says “both of us are knaves”, we know A is a knave and B is a knight. If A was a knight, then they’d both be knaves, which is a contradiction, so A is knave. Then we know “both of us are knaves” is false, which means at least one person is a knight. Since A is already a knave, B must be a knight. On the other hand, if A said “both of us are the same”, it would also be a valid for both of them to be knights.

Knights and Knaves puzzles are supposed to be solved through creativity and cleverness: you read the statements and figure out the contradictions. Let’s instead take all the fun out and solve them with a program.

Alloy

We’re going to use Alloy for this. I’ve talked extensively about Alloy here, but that was in regards to modeling complex relational problems. We don’t need that here. Instead, Alloy shines because of its model-finding abilities. Not only can it find errors in our spec, it can find examples that satisfy our spec. More importantly it can find all matching models, so we can see if a given puzzle has multiple solutions.1

First, the types:

abstract sig Person {}sig Knight extends Person {}sig Knave extends Person {}

By saying Person is an abstract signature, there are no people who aren’t Knights or Knaves. In this case Knight and Knave are disjoint, so nobody can be both. This isn’t a strict requirement of the Alloy type system, as we’ll see later. This all means that Knight + Knave = Person: the set of knights, unioned with the set of knaves, is equal to the set of people.

Now we’ll define a predicate that corresponds to a puzzle:

pred Puzzle { #Person = 2

The first line says that there are exactly two people. Remember, since Knight and Knave are disjoint covering subsets of the Person set, saying there are two people also means that #(Knights + Knaves) = 2.

 some disj A, B: Person {

After that we want to place conditions on the two people. We say the two people are disj because otherwise Alloy could select A = B.

 A in Knight <=> (A + B) in Knave

This might take some unpacking, so I’ll build it up iteratively. First of all, P <=> Q is the logical statement “P is true if and only if Q is true”, or more intuitively, “P and Q are either both true or both false”. P <=> Q might not be true! If it isn’t, then we have “If P is true then Q is false, and vice versa”. By making P <=> Q part of our predicate, it must be true for our predicate to be true. Since our predicate corresponds to a Knights and Knaves solution, finally, our predicate holding means we found a correct solution.

Now we have A in Knight <=> Q. Since the clauses are both true or both false, if A is a knight then Q will be true. But if A is a knave, then !Q is true. Every clause associated with a knight is true, and every clause associated with a knave is false.

Finally, we have A in Knight <=> (A + B) in Knave. So this says either A is a knight and both A and B are knaves, or A is not a knight and it’s not the case that both A and B are knaves. We could have also written Knave = Person, which would have the same meaning.

 }}run Puzzle for 10

for 10 means up to ten of each signature (in this case, people) can be in the model. We’ve already capped the number of people at 2 as part of the predicate. I did 10 so that I could freely tweak the problem without having to change the model finder. Final model:

abstract sig Person {}sig Knight extends Person {}sig Knave extends Person {}pred Puzzle { #Person = 2 some disj A, B :Person { A in Knight <=> (A + B) in Knave }}run Puzzle for 10

Running it gives us a valid solution:2

A: KnaveB: Knight

Alloy is unable to find any more matching models, so there’s exactly one correct solution to this puzzle. We could also try “we are both the same”:

- A in Knight <=> (A + B) in Knave+ A in Knight <=> (A + B) in Knave or (A + B) in Knight

Alloy finds two solutions:

A: KnightB: KnightA: KnaveB: Knight

Which is as we expected.

Some logic weirdness

Propositional logic is weird and often unintuitive. To show this, imagine if A instead said “I am a knave and B is a knave.”

A in Knight <=> A in Knave and B in Knave

This gives us the same answer as before. But if A said “I am a knave. B is a knave”, is that the same?

A in Knight <=> A in Knave A in Knight <=> B in Knave

Alloy can’t find a solution for this! This is different from before because the opposite of A & B is !(A & B), and !(A & B) != !A & !B. Our first clause is then A <=> !A, which is impossible to satisfy.

Let’s make it even stranger. What if we had just one person, who said “I am a knave”?

pred Puzzle { #Person = 1 some disj A: Person { A in Knight <=> A in Knave  }}

This is, as before, unsatisfiable. But what if A said “If you asked me, I would say I was a knave”? If “I claim X” is the logical statement A in Knight <=> X, then “I claim ‘I claim X’” is the logical statement A in Knight <=> (A in Knight <=> X). The predicate is then

 A in Knight <=> (A in Knight <=> A in Knave)

Which has a valid solution if A is a knave. This means, confusingly enough, that if we want to know whether P is true or false, we don’t need to know whether we’re talking to a knight or a knave. Both of them will answer “If I asked you, would you claim P” as if they were a knight. We can test this by importing the helper module boolean, and then checking that everybody, regardless of their orientation, will give the correct answer:

open util/booleanabstract sig Person {}sig Knight extends Person {}sig Knave extends Person {}assert Question { all p: Person, b: Bool { b.isTrue <=> (p in Knight <=> (p in Knight <=> b.isTrue)) }}check Question //instead of run Puzzle

We use an assert instead of a pred because we’re not interested in finding specific examples where the works. We’re interested in finding counterexamples where this doesn’t work. But we don’t find any, which means everybody answers the question truthfully.

Some more examples

I grabbed some Knights and Knaves puzzles from here.

Problem 1: There are two native islanders, named Alice and Bob, standing next to each other. You do not know what type either of them is. Suddenly, Alice says “At least one of us is a Knave.”

pred Problem1 { #Person = 2 some disj A, B: Person { A in Knight <=> #Knave >= 1 }}
A: KnightB: Knave

Problem 2: Again, there are two native islanders standing next to each other. One is named Claire and the other is named Desmond. You do not know what type either of them are. Claire suddenly says, “We are both Knights”. After this, Desmond says “Either Claire is a Knight or I am a Knight, but we are not both Knights.

pred Problem2 { #Person = 2 some disj C, D: Person { C in Knight <=> Knight = C + D D in Knight <=> (C in Knight or D in Knight) and Knight != C + D  }}
C: KnaveD: KnightC: KnaveD: Knave

Problem 3: There are three native islanders, named Elena, Fernando, and Gary, standing together. You ask Elena, “How many knights are among you?”, and Elena answered but you couldn’t quite hear what she said. You then ask Fernando, “What did Elena say?”, and Fernando replies, “Elena said there is one knight among us.” At this point, Gary says “Don’t believe Fernando; he is lying.”

I don’t like this one. The PDF thinks it means this:

pred Problem3 { #Person = 3 some disj E, F, G: Person { F in Knight <=> (E in Knight <=> #Knight = 1) G in Knight <=> F not in Knight }}
E: KnaveF: KnaveG: KnightE: KnightF: KnaveG: Knight

But this is actually wrong! If F is a knave, then E didn’t say ‘there’s one knight among us.” The PDF assumes that she said something that’s incompatible with it, aka F is a knave and E is a knight, we can infer there is not exactly one knight. The problem is that all we can infer from “F is a knave” is “E did not say ‘there is one knight among us.’” It does not restrict what E said, or what she could say later. We could have had the following:

You: "How many knights are among you?"E: "I'm hungry."You: "What did E say?"F: "E said there is one knight among us."

To accurately capture the logic of the problem, we need to make the following adjustment:

- F in Knight <=> (E in Knight <=> #Knight = 1)+ F in Knight => (E in Knight <=> #Knight = 1)

If F is a knight, then E made that claim. If F is a knave, we can infer nothing. In this case the two predicates give equivalent answers. For a case where using <=> instead of => gives the wrong answer, try replacing F’s statement with “E said there is at least one knight.”

Problem 4: You travel along a road that comes to a fork producing a path to the right and a path to the left. You know that one path leads to Death and the other path leads to Freedom, but you have no idea which is which. You can only choose one path to follow. Fortunately, at the fork in the road are two native islanders, named Horace and Ingrid. You know that one of Horace and Ingrid is a Knight and the other is a Knave, but you don’t know which is which. You are allowed to ask only one question. You can ask either Horace or Ingrid (but not both), and the person you ask will answer you.

This is the most famous Knights and Knaves puzzle. We can’t just plug everything in because we aren’t provided with the answers to check. We instead need to figure out a question to ask. We can test, though, if a given question works or not. “Works” here means that regardless of who we ask, we can use the answer to consistently find the right path. Since we can only ask one question, this means finding a question that both always answer the same way.

The usual solution is “ask them what the other would say is the path to Freedom”.

assert Problem4 { #Person = 2 and #Knave = 1 implies all p: Person, b: Bool | //is b the path to freedom? let o = Person - p { //the other one (o in Knight <=> (p in Knight <=> b.isTrue)) <=>  (p in Knight <=> (o in Knight <=> b.isTrue)) }}

They answer this consistently… and falsely. If b is the path to freedom, they will both say b leads to death, You have to invert their answer.

- (o in Knight <=> (p in Knight <=> b.isTrue)) <=> - (p in Knight <=> (o in Knight <=> b.isTrue))+ b.isFalse <=> (p in Knight <=> (o in Knight <=> b.isTrue))

The other problem is that this only works if we have exactly one knight and one knave. If we have two knights or two knaves, they will answer truthfully.

- #Person = 2 and #Knave = 1 implies+ #Person = 2 and (Person = Knight or Person = Knave) implies- b.isFalse <=> (p in Knight <=> (o in Knight <=> b.isTrue))+ b.isTrue <=> (p in Knight <=> (o in Knight <=> b.isTrue))

It’s really funny to me that the famous solution only works in this special case, while the general case is both simpler and always gets true answers regardless of what pair you have.

- b.isWhatevs <=> (p in Knight <=> (o in Knight <=> b.isTrue))+ b.isTrue <=> (p in Knight <=> (p in Knight <=> b.isTrue))

Not only that, but the general case doesn’t even use o! It works even if we’re talking to a single person.

Advanced Knights and Knaves

These puzzles can get a lot trickier. One way is by adding another layer of properties. For example, in addition to being a knight or a knave, a given person is also either drunk or sober. Sober people act normally, drunk people believe false things are true and true things are false. For example, if you asked a drunk knight “are you a knight”, they will believe they are a knave, and will truthfully (in their mind) answer “no, I am a knave”. By contrast, if you ask a drunk knave “are you a knight”, they will believe they are a knight, and will lie and answer “no, I am a knave”.

Making two signatures extend an abstract type make them mutually exclusive. Instead, we want to say that each of our four qualifiers is in the abstract type. That way they are not mutually exclusive.

- sig Knight extends Person {}- sig Knave extends Person {}+ sig Knight, Knave, Drunk, Sober in Person {}

We want to declare Knight/Knave are mutually exclusive, as are Drunk/Sober. We also want to say that everybody belongs to both categorizations. We can do this with a fact.

fact { Person = (Knight + Knave) & (Drunk + Sober) no (Knight & Knave) + (Drunk & Sober) }

A person tells the truth if they are a sober knight or a drunk knave. Writing p in (Knight & Sober) + (Knave & Drunk) will get tiring after a while. We should pull it out into it’s own claims predicate of form p.claims[statement]. However, all arguments to predicates must have a signature type, and logical expressions aren’t typed. We could instead express it as p.claims <=> statement, or we could use a macro:

let claims[p, bool] { p in (Knight & Sober) + (Knave & Drunk) <=> (bool)}

We can now use this to find solutions for the new setup:

pred Puzzle { #Person = 1 some disj A: Person { A.claims[A in Knave] }}
A: Drunk KnightA: Drunk Knave

Other variations of the puzzle, such as day and night knights or knights/knaves/spies are also easy to include in this format.

  1. Some FM folks don’t see model finding as that different from model checking. If you want to find a model that satisfies x, you can just write a spec that claims !x and find a counterexample. But model-checking should consistently return the same counterexample, while model-finding should return a set of matching examples. [return]
  2. The output is as a visualized graph but I’m too lazy to embed images here. [return]

FAQs

How do you solve knight and knave problem? ›

In Labyrinth, the protagonist's solution is to ask one of the guards: "Would [the other guard] tell me that [your] door leads to the castle?" With this question, the knight will tell the truth about a lie, while the knave will tell a lie about the truth.

What are the rules of the island of knights and knaves? ›

Knights only tell the truth, while Knaves only tell lies. There are many variations of this puzzle, but most involve asking a question to figure out who is the knight and who is the knave.

How many knaves are there? ›

A knave can say "we're all knaves" if and only if there's at least one knight among them. (On the other hand a knight can never say "we're all knaves". And nobody can say "I'm a knave"). Write out all possibilities - there are only 8 of them.

Can a knight hit every square? ›

Yes. A Knight's Tour covers every square of the board just once. Moving from a8 through h1 and touching all the squares on the board without any restrictions on the number of repeated moves would just be a particular example of that calculation.

Who is the knight who the knave and who the spy? ›

The knight always tells the truth, the knave always lies, and the spy can either lie or tell the truth. You meet each of these three people, but not necessarily in that order. The first person you meet says “I am the knight”. The second person you meet says “I am the knave”.

What are 2 rules the Knights of the Round Table? ›

Never to break faith for any reason. To practice religion most diligently. To grant hospitality to anyone, each according to his ability.

What are A and B if A says B is a knight and B says the two of us are opposite types? ›

Answer: A is a knight. B is a knave. A says “The two of us are both knight” and B says “A is a knave.”

What do knaves represent in the poem? ›

Answer: Knaves represent scoundrels, liars or conman.

Is the Jack the page or the knight? ›

The page became the jack. the jack.) (If you look at the jack in most decks, he looks like a knight.)

What job is a knave? ›

A male domestic worker, a person who works within the employer's household (kitchen boy in Middle English)

Is a knave a prince? ›

In Shakespeare, an important person like a king or a prince might call a thief a knave.

Is two knights worth a rook? ›

In the endgame, a rook and one pawn are equal to two knights; and equal to or slightly weaker than a bishop and knight.

Is 4x4 knights tour possible? ›

For example, on a 4x4 chessboard a knight's tour is also impossible. In fact, the 5 × 6 and the 3 x 10 chessboards are the smallest rectangular boards that have knight's tours.

Can pawn capture a knight in front of it? ›

The pawn may capture either the rook or the knight, but not the bishop, which blocks the pawn from moving directly forward.

Who is the leader in Knights? ›

Tsukasa is the leader of NEW DIMENSION's Knights.

Is knave a knight in Tarot? ›

The knave is often depicted as a foot soldier or squire to the knight. Many early tarot decks had added female ranks into the face cards including the Cary-Yale deck which added queens, mounted ladies, and maids as counterparts to the males.

Who was the servant to the knight? ›

In medieval times, a page was an attendant to a nobleman, a knight, a governor or a Castellan. Until the age of about seven, sons of noble families would receive training in manners and basic literacy from their mothers or other female relatives.

Who is the strongest in the Knights of the Round Table? ›

Galahad, in both the Lancelot-Grail cycle and in Malory's retelling, is exalted above all the other knights: he is the one worthy enough to have the Grail revealed to him and to be taken into Heaven.

Can we mate with 2 knights? ›

In general, two knights cannot force checkmate, but they can force stalemate. Three knights can force checkmate, even if the defending king also has a knight or a bishop. Edmar Mednis stated that this inability to force checkmate is "one of the great injustices of chess."

What are the 5 codes of chivalry? ›

The Nature of Chivalry

The ideals of Christian morality and knightly chivalry are brought together in Gawain's symbolic shield. The pentangle represents the five virtues of knights: friendship, generosity, chastity, courtesy, and piety.

Does A and B MEAN A or B? ›

In mathematics the use of "and" also deserves a brief discussion, although its use agrees with the everyday use. Just as we would expect, the phrase "A and B" means that both A and B must hold.

How do you negate a logical statement? ›

The symbols used to represent the negation of a statement are “~” or “¬”. For example, the given sentence is “Arjun's dog has a black tail”. Then, the negation of the given statement is “Arjun's dog does not have a black tail”. Thus, if the given statement is true, then the negation of the given statement is false.

Are the statements it will not rain or snow and it will not rain and it will not snow logically equivalent? ›

Are the statements, “it will not rain or snow” and “it will not rain and it will not snow” logically equivalent? Since in every row the truth values for the two statements are equal, the two statements are logically equivalent.

Do knaves twist the truth should you consider all men equally important? ›

Knaves twist the truth for their own benefit and to make a trap for fools. You should consider all men equally important to be a humble and good human being.

What lesson speaker is conveying in the poem If? ›

In this poem, Kipling's speaker personifies triumph and disaster. He calls them imposters as both of these events don't last long.

Why do knaves twist the truth? ›

Answer: When Rudyard Kipling says, "If you can bear to hear the truth you've spoken twisted by knaves to make a trap for fools," he means that sometimes, even when you speak the truth, others will change your words to hurt others or convince others of untrue things.

Is Jack called Joker? ›

Jack Napier, also known as the Joker, is a fictional character introduced in the 1989 superhero film Batman, directed by Tim Burton.

Why are jacks called jacks? ›

jacks, also called jackstones, fivestones, or dibs, game of great antiquity and worldwide distribution, now played with stones, bones, seeds, filled cloth bags, or metal or plastic counters (the jacks), with or without a ball. The name derives from “chackstones”—stones to be tossed.

Is Jack lower than queen? ›

(a) The rank of the cards used in all types of poker other than low poker, for the determination of winning hands, in order of highest to lowest rank, shall be: ace, king, queen, jack, 10, nine, eight, seven, six, five, four, three and two. All suits shall be considered equal in rank.

Is knave a rogue? ›

1. Knave, rascal, rogue, scoundrel are disparaging terms applied to persons considered base, dishonest, or worthless. Knave, which formerly meant merely a boy or servant, in modern use emphasizes baseness of nature and intention: a dishonest and swindling knave.

What is opposite knave? ›

Antonyms are words which have opposite meaning in comparison to the other. Option B)sincere is correct as the word sincere means free from pretence or deceit; proceeding from genuine feelings and the word knave means a dishonest or unscrupulous man. Both the words are opposite of each other.

How do you pronounce knave? ›

Break 'knave' down into sounds: [NAYV] - say it out loud and exaggerate the sounds until you can consistently produce them.
...
Below is the UK transcription for 'knave':
  1. Modern IPA: nɛ́jv.
  2. Traditional IPA: neɪv.
  3. 1 syllable: "NAYV"

What is Jack short for? ›

Jack is a given name, a diminutive of John. Since the late 20th century, Jack has become one of the most common names for boys in many English-speaking countries. It may also be a short form of the male name Jackson.

What does the J card stand for? ›

playing cards. Ranks are indicated by numerals from 1 to 10 on “spot cards.” In addition, three court cards designated jack (formerly knave), queen, and king are notionally equivalent to 11, 12, and 13, respectively, though actually marked J, Q, and K.

How many jacks are in a 52 card? ›

4 Jacks, and . A standard deck of cards contains 52 cards.

What is Knight's Tour and who solved it? ›

The knight's tour as solved by the Turk, a chess-playing machine hoax. This particular solution is closed (circular), and can thus be completed from any point on the board.

What is the Knight's challenge? ›

What is KNIGHT? The goal of the KNIGHT challenge is to facilitate the development of Artificial Intelligence (AI) models for automatic preoperative prediction of risk class for patients with renal masses identified in clinical Computed Tomography (CT) imaging of the kidneys.

What is the Knights Tour problem? ›

The "Knight's Tour" problem is to move a knight on a chessboard so that all sixty-four squares are jumped on only once. A knight's tour is said to be 'dosed' or're-entrant' ifposition '1' is a knight's move away from position '64'.

How many squares does a knight control? ›

Compared to other chess pieces, the knight's movement is unique: it may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an "L").

What ended the knights? ›

By the mid to late 16th century, knights were quickly becoming obsolete as countries started creating their own professional armies that were faster to train, cheaper to equip, and easier to mobilize.

What does N mean chess? ›

Each piece type (other than pawns) is identified by an uppercase letter. English-speaking players use the letters K for king, Q for queen, R for rook, B for bishop, and N for knight (since K is already used and is a silent letter in knight).

Why does the Green Knight swing three times? ›

The Green Knight explains that the reason that Gawain is tapped is because the third time he withheld a part of his earnings for the day (the green belt). The Green Knight swings two times, stopping short; on the third time, he taps Gawain, scarring him but not chopping off his head.

Why does the Green Knight strike three blows? ›

The Green Knight then reveals himself to be an alter ego of the lord of the castle, Bertilak de Hautdesert, and explains that the three axe blows were for the three occasions when Gawain was visited by the lady.

How many times does the Green Knight swing the axe? ›

For example, three kisses are exchanged between Gawain and Bertilak's wife; Gawain is tempted by her on three separate days; Bertilak goes hunting three times, and the Green Knight swings at Gawain three times with his axe.

Why do knights no longer exist? ›

End of the Knight

One reason was that many countries had formed their own standing armies. They paid soldiers to train and fight. They no longer needed lords to come fight as knights. The other reason was a change in warfare.

How do you do the knights Tour puzzle? ›

Form the first position; calculate all the possible moves, pick one move and then keep repeating until reach a solution or a non solution. A non solution means the knight may be trapped in some square with all the possible moves from that square are already taken (have been move to before).

How many solutions are there to the knight's Tour? ›

4/10/2019 – You know what the Knight's Tour is: move the knight so it visits every square of the chessboard just once. There are around 30 trillion ways to do this, but it is certainly not easy for humans to execute a single one correctly — least of all blindfolded and starting from a random square.

Can a rook beat a knight? ›

Rook versus a knight: this is usually a draw. There are two main exceptions: the knight is separated from the king and may be trapped and won or the king and knight are poorly placed. Kamsky vs Bacrot, 2006 is an example of a rook vs knight ending which resulted in a win.

Is the knight stronger than the rook? ›

The rook is stronger because it can controls a whole file and/or rank. The knight can sometimes control squares that are "unnecessary," (not that the rook can't but the rook gets more squares to control).

Is a knight worth a rook? ›

Traditionally, a rook is worth 5 points, and a knight and bishop are worth 3 points. So you gain 1 point worth of material by this trade. In practice, though, it's a questionable trade, because it's a lot easier to force checkmate with a rook than with a bishop and a knight.

Top Articles
Latest Posts
Article information

Author: Fr. Dewey Fisher

Last Updated: 12/04/2022

Views: 5870

Rating: 4.1 / 5 (42 voted)

Reviews: 89% of readers found this page helpful

Author information

Name: Fr. Dewey Fisher

Birthday: 1993-03-26

Address: 917 Hyun Views, Rogahnmouth, KY 91013-8827

Phone: +5938540192553

Job: Administration Developer

Hobby: Embroidery, Horseback riding, Juggling, Urban exploration, Skiing, Cycling, Handball

Introduction: My name is Fr. Dewey Fisher, I am a powerful, open, faithful, combative, spotless, faithful, fair person who loves writing and wants to share my knowledge and understanding with you.