Hacker Challenge: Prune and Search

Learn to devise efficient solutions to the knights and knaves problem through logical thinking.

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 100100 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.

Get hands-on with 1200+ tech skills courses.