River Crossing and State Space Search

image

I made a small 10 min demo to simulate the classic river crossing puzzle for teaching state space search in my AI class. I did exercise my right to be creative by changing the characters a bit. Jerry, Tom and Spike have to cross a river, going from the right side to left, in a boat. While you are in the boat, they behave. But as soon as you leave Tom with Jerry or Tom with Spike on one side WITHOUT the boat, they start fighting. Being a peace loving person, you don’t want that. The goal is to move them across the river with no fights. (as you may have noticed, there is no eating/killing involved in my version)

Here, we can represent each object by a Boolean variable and draw the states accordingly. The picture above can be represented by 1 0 1 0 where the left most 1 represents that the boat is on the left bank and the zero after that tells that Jerry is on right one. Similarly the next 1 and 0 denote Tom on the left bank and Spike on the right one respectively.Here is a link to the executable in case anyone wants to play it or give it to a kid to figure out. Drop me an email if you want the source code (C#). The executable requires an installation of the Microsoft .NET framework 3.5.

Download River Crossing Puzzle

Microsoft .NET framework 3.5

2 thoughts on “River Crossing and State Space Search

Leave a Reply

Your email address will not be published. Required fields are marked *