Hacker Challenge: Prune and Search

In this lesson, we will employ the prune and search technique to solve a knights and knaves problem.

The “Hacker Challenge” lessons throughout the course are optional and can be skipped. However, they would help strengthen the respective concepts.

Knights and knaves

On a faraway island, there are a total of $100$ tribesmen. Every tribesman on this island is either a knave (Faker) or a knight (Trustworthy). We need to figure out who is a Faker and who is a Trustworthy person. We can ask each of the tribesmen questions about who is Trustworthy and who isn’t. Moreover, we can ask as many questions as we want. The only information known is that the number of knights is greater than the number of knaves.