Using Search Algorithm in Python to solve the 3 Wolves and 3 Lambs puzzle

Question

I was thinking about this question for a long time and couldn't figure out how to solve it.

The problem is as following:

We have 3 lambs and 3 wolves in a side and we have to let them pass the river to the other side. In the beginning it looked easy till i stopped with these difficult circumstances:

• The wolves can't be more than the lambs, which means the lambs can be more than or equal to the wolves.
• The boat, which carries the animals to the other side, can't carry more than 2
• The boat MUST be always carrying animals, which means you can't move an empty boat.

The question has to be solved by search algorithm, like A* or BFS etc.

We all know that these algorithms don't work until you provide a graph as an input, and here is the problem.

How we can create a graph from 3 lambs and 3 wolves?

I though about it many times, and the only way came to my mind is by all the possibilities. Sounds good for me, but still doesn't give me any progressing because the problem still the same, how to implement it or write it as a Python code to pass this graph to the algorithm so the algorithm can solve it?

Answer 1

Suppose each node has a state on it representing how many lambs and wolves are on the left bank and whether or not the boat is on that bank ('0' for left, '1' for right).

The initial node is:

Node 0 : { lambs:3, wolves:3, boat:0 }

From here you can travel to any node that meets the requirements. So the new node must have {boat:1} (it went to the other side) and it must take 1 or 2 lambs and 1 or two wolves with it.

The next possible nodes are:

Node 1 : { lambs:2, wolves:3, boat:1 }  // boat took one lamb
Node 2 : { lambs:1, wolves:3, boat:1 }  // boat took two lambs
Node 3 : { lambs:2, wolves:2, boat:1 }  // boat took one lamb and one wolf
Node 4 : { lambs:3, wolves:1, boat:1 }  // boat took two wolves
Node 5 : { lambs:3, wolves:2, boat:1 }  // boat took one wolf

And so on. You can generate these dynamically as you explore the tree of possible moves. And, as Erick points out in the comments, some of these aren't legal according to the rules and should not have been in the graph. I'll leave that to you to figure out.

The ending node is:

Node N : { lambs:0, wolves:0, boat:1 }

The key takeaway is that you need a graph between possible states not a graph between the sides of the river or the animals. And each state needs to capture everything in the 'world' model.

In pseudo C# code:

public class Node
{
     public int LambsOnLeft {get; set;}
     public int WolvesOnLeft {get; set;}
     public int Boat {get; set;}

     public IEnumerable<Node> NextStates()
     {
         if (Boat == 0)    // on left
         {
              // boat takes  one lamb from left to right
            if (LamsOnLeft > 0 && LambsOnLeft-1 >= WolvesOnLeft)     
              yield return new Node(LambsOnLeft-1, WolvesOnLeft, 1);
            }
            if (LambsOnLeft > 1 && LambsOnLeft-2 >= WolvesOnLeft)
              yield return new Node(LambsOnLeft-2, WolvesOnLeft, 1);
            }
            // take one wolf
            if (WolvesOnLeft > 0)
                yield return new Node(LambsOnLeft, WolvesOnLeft-1, 1);
            // take two wolves
            if (WolvesOnLeft > 1)
               yield return new Node(LambsOnLeft, WolvesOnLeft-1, 1);
            ...
        }
     }
}