Ferryman Problem
From Wiki Notes @ WuJiewen.com, by Jiewen Wu
Problem Statement
The ferryman problem is popular, which has many variants. It seeks a solution to the following synopsis.
A ferryman wants to take his goods, i.e., a goat, a cabbage and a wolf to the other side of a river. He can take at most one of the three things in the boat to cross the river. Note that the following pair cannot stay together unless they are under the supervision of the ferrymen: (goat, cabbage) (wolf, goat). Otherwise, the ferrymen will lose one of them in each pair. Now we are looking for a solution for the ferryman to transport all goods to the other side without any loss.
To solve the problem by Model Checking, we are asked to check if a solution is possible, i.e., a decision problem requiring only YES or NO.
Solution
Reference
- Notes from Elvinia Riccobene at Università di Milano.
