The Knights and Knaves Express

kke.md

It's time to drag the Island of Knights and Knaves kicking and screaming into the 19th century! We're going to run a train. For these puzzles, you'll have a set of stations with possible connections, and you need to find a route that starts at one station, goes through every other station exactly once, and ends in a station. IE if our map was

A -- B -- C
|    |    |
D -- E -- F

Valid routes might be A B C F E D, or A D E B C F, but A B E D C F is invalid. The ordering matters: A B C is a different route from C B A.

But also, every station is run by either a Knight or a Knave. The stationmaster has a set of requirements for the route. Knights tell the truth about their requirements, but Knaves always lie. You must plan the route so that every requirement by a Knight is satisfied, and every requirement by a Knave is unsatisfied. IE if we have

A --- B
|     |
-- C --

If C says "I must come first", if C is a Knight, then the route starts at C. But if C is a knave, the route does not start with C.

Problem 1

At least one of the two stationmasters is a Knave.

A -- B

A: "Start at my station."

B: "End at my station."

Problem 2

Two of the stationmasters are knights, two are knaves.

A -- D
|    |
B -- C

A: "The route must connect to me right after a Knave's station."

B: "I should come at some point before C."

C: "Make sure the two knights are adjacent to one another: one has to come right after the other."

D: "A and B should both come at some point before me."

B (again): "Oh, also: I should come at some point after A."

Problem 3

   A
 /   \
B --- C

A: "Don't put Raymond right before me."

B: "Don't put Raymond right after me."

C: "Don't put Raymond right before or right after me."

You: "What's wrong with Raymond?"

A: "He's an asshole and a Knave."

B: "He wears sunglasses indoors."

C: "He calls himself a 'singer-songwriter'."

A: "Also he smells bad."

B: "He smells so bad. Like 'rotting socks' bad."

(Assume one of them is Raymond)

The annoying thing with these is that I want people to express requirements like "If X is true, then do Y". That's formally X => Y, but the negation is X /\ !Y. What I want is that if the person is a Knave, you have to satisfy X => !Y.