Introduction

This project is about solving a puzzle of Prisoners and Hats by logical reasoning of multi agent systems. The problem describes four agents (prisoners) and a correct strategy to the puzzle by the prisoners could save all the four lives. We decided on this problem, because the main goal of the project was to analyse the logical reasoning behind the correct solution.

The project is divided into four different sections. In our first section Home we describe the situation and consequences of the solutions of the puzzle. In the second section called Analysis, we explain the logical reasoning behind the problem. For analysis we use Kripke structures and epistemic formulae. In section three Solution and Conclusions we give the correct solution to the puzzle. In this section we also discuss our conclusion and future work. In section four Demo we provide a java program users to experiment with the puzzle and we also provide a sample result of it.

The puzzle

There are four prisoners arrested for a crime and the jail is full. Therefore the jailor decides to present a puzzle.

The jailor puts three prisoners in a row and one behind the screen, such that he is not visible to the rest. He gives party hats to all the prisoners. Each prisoner only sees the hat on the men in front of him. The fourth man cannot see the rest. There is no communication permitted among the prisoners.

If any of the prisoners is able to correctly tell the colour of his own hat, all of them would be set free, else all of them would be executed. The puzzle is to find the right strategy to solve the puzzle irrespective of how the jailor distributes the hats.

Read more »