Back to Feed
•ProjectsOther

CS50AI - Knights and Knaves logic puzzle

Check out the code for this project here

Solving Knights and Knaves programatically

Knights and Knaves are a famous kind of logic puzzle created by Raymond Smullyan where you have two types of characters: Knights who always tell the truth and Knaves who always lie. With this you can create a lot of different interesting riddles. Here I built a python program to try and solve some of these reasoning problems.

I made this as a project as part of Harvard's CS50’s Introduction to Artificial Intelligence with Python. The way that I build this algorithm was using a knowledge-based agent which is not something that searches a path or plays a game but knows facts and then uses the rules of logic to derive new useful truths.

2023-11-12-knights-and-knaves credit

The Architecture

Here I have to first translate logical English statements into mathematical statements I can put in code.

Firstly I define the base propositions as Symbol objects in Python:

  • AKnight represents the English sentence "Person A is a Knight."

  • AKnave represents the English sentence "Person A is a Knave."

The next thing we had to encode in the program is the fundamental logical connective statements (And, Or, Not, and Implication). We then need to tell the program that a person must be either a Knight or a Knave but cannot be both at the same time. We can implement that with this statement:

And(Or(AKnight, AKnave), Not(And(AKnight, AKnave)))

The Mechanics

We can use the Implication statement to define the possibilities of different statements:

  1. Implication(AKnight, And(AKnave, BKnave)) — If A is a Knight, what they said must be true.

  2. Implication(AKnave, Not(And(AKnave, BKnave))) — If A is a Knave, what they said must be false.

I then have main function that actually solves the logic puzzle. Here is how it works:

  • Generate all possible realities: The programs creates a truth table for all possible combinations of Knights and Knaves.

  • Test the Knowledge Base: The program takes its Knowledge Base(the statements we made earlier) and tests it against every single possible reality that we generated above.

  • Final check: The algorithm then filters out all the universes that contradict our established facts giving us the remaining statements that are true.

Looking back

A major issue with this program is that if we scaled up the number of characters it would quickly become very difficult to solve. Even adding just 30 characters would require the computer to evaluate over billions of cases.

This was a fun way to learn about these logic puzzles and a way to learn how to solve them. It was a good way to develop my skills in Python and also more generally in mathematics and computer science.