Night Hour

Reading under a cool night sky ... 宁静沉思的夜晚 ...

Farmer Wolf Cabbage Sheep River Crossing Puzzle

Plant Zenstones

An expert is a person who has made all the mistakes that can be made in a very narrow field , Niels Bohr


29 May 2017


Introduction

Farmer, wolf, cabbage, sheep is a famous river crossing puzzle. The puzzle goes like this, a farmer wants to move a wolf, cabbage and sheep across a river. The farmer has only a small boat that can sit himself and one passenger. The wolf will eat the sheep if the farmer is not around. The sheep will eat the cabbage if the farmer is not around. How can the farmer ferry all of them across the river ?

The puzzle can be treated as a graph search problem and be solved using either breadth first search or depth first search. This article shows how to build a simple java application that solves this.

Design and Approach

The river crossing puzzle can be viewed as a sequences of states. In the initial state, the farmer, wolf, cabbage and sheep are on one bank of the river (say left side) and the opposite river bank (right) is empty. From this initial state, there are a possible number of moves that the the farmer can take to transition to the next state. For example, the farmer can row himself and the wolf across. This creates a new state where the cabbage and sheep are together on one side of the river, while the farmer and wolf are on the other side. Based on the earlier rules and constraints, the sheep will eat the cabbage; and the farmer fails in his task to bring everything across the river. Therefore moving the farmer and wolf lead to a state that cannot be allowed. Other moves such as, farmer together with cabbage, farmer alone, farmer with sheep can be considered in turn.

When a new state that is allowable is created, additional moves from this state can then be considered and so on, until the solution is reached; or no other moves leading to an allowable new state is possible. The solution is a state where the farmer, wolf, cabbage and sheep are all on the opposite bank of the river from where they started. The following diagram illustrates the state transitions.

River crossing puzzle state transitions
Fig 1. State Transitions

Notice that a move that transits to a repeated state that has already occurred in its parent path is not allowed. This is to prevent an endless loop of repetitions.

Breadth First and Depth First Search

The state space described above can be generated by breadth first search or depth first search algorithm. In breadth first search, the parent state is explored, followed by the next level consisting of its children and then the next level of its grand children and so on ... It goes level by level, exploring all the states at a particular level before proceeding to the next level. The number of possible moves/transitions from each state to a new state is the branching factor. In this puzzle, it is 4 or less moves (F, FW, FS, FC). Breadth first search has a large memory space requirements and time complexity of O(b d +1) where b is branching factor and d is depth or level.

Depth first search on the other hand, goes down the deepest path until a solution is found or no possible moves can be made. It then backtracks up and try the next path. This process continues until the entire search space has been explored. Depth first search requires less memory space than breadth first and it has a time complexity of O(bd) where b is branching factor and d is the depth of the search tree.

Breadth First and Depth First Search
Fig 2. Breadth First and Depth First Search

An enhanced version of depth first search is iterative deepening depth first search. This techniques utilizes depth first search but with an increaing depth limit for each iteration. For example, in the first iteration, it expands using depth first search using a depth limit of 1, if no solution found, it goes into the next iteration and uses a depth limit of 2 and so on ... until solutions are found or the maximum allowable depth limit is reached.

Implementation

The application consists of a single FarmerWolfCabbageSheep class file with two inner classes, State and Node. The State class represents that possible states of the puzzle at any one time. For example, the initial state where the farmer, wolf, cabbage and sheep are all on one side of the river. The Node class are used for constructing the state graph containing the various states arising from the moves/transitions.

The following snippet shows the State inner class. The method isAllow() checks if the state is an allowable state where the constraints and rules are met. The isSolution() method checks if it is a solution state. The transits() method creates a new state based on the move.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
   /**
     * Private Inner State class to represent a state A state consists of the
     * occupants (farmer, wolf, sheep, cabbage) on the left and right bank of
     * the river One of the river bank (left or right) is where the farmer is
     * located and from here the farmer can cross the river to the opposite bank
     * optionally bringing along another occupant(wolf , sheep, cabbage)
     * 
     * It is assumed that the initial state is
     * 
     * left bank: farmer(F), wolf(W), cabbage(C), sheep(S) right bank:
     * 
     * All occupants including the farmer is on the left bank and the right bank
     * is empty. The farmer will attempt to move everyone to the right bank
     * through a sequence of crossings subjected to the constraints in the
     * puzzle. Farmer can at most move one more occupant besides
     * himself/herself. Wolf , sheep cannot be together without farmer. Cabbage,
     * sheep cannot be together without farmer. The solution state will be
     * 
     * left bank: right bank: farmer (F), wolf(W), cabbage(C), sheep(S)
     * 
     * The left bank is empty and all the occupants farmer, wolf, cabbage and
     * sheep are on the right bank.
     *
     */
    private class State
    {
        private String bank; // The active bank where the farmer is currently
                             // located
        private TreeSet<String> left, right; // left and right bank with its
                                             // occupants.

        public State(String bank, TreeSet<String> left, TreeSet<String> right)
        {
            this.bank = bank;
            this.left = left;
            this.right = right;
        }

        /**
         * Takes a TreeSet<String> that contains the occupants in a river bank
         * (left or right) and check whether the puzzle constraints Wolf , sheep
         * cannot be together without farmer Cabbage, sheep cannot be together
         * without farmer are met.
         * 
         * @param b An TreeSet<String> representing the river bank with its
         *            occupants
         * @return true if puzzle constraints are met, false otherwise.
         */
        private boolean checkAllowBank(TreeSet<String> b)
        {
            // Wolf and Sheep together without Farmer
            if (b.contains("W") && b.contains("S") && (b.contains("F") == false))
                return false;
            // Sheep and Cabbage together without Farmer
            if (b.contains("S") && b.contains("C") && (b.contains("F") == false))
                return false;

            return true;
        }

        /**
         * Public method to check if a State meets the puzzle constraints.
         * Disallow states are those that doesn't meet the puzzle constraints.
         * 
         * @return true if a State is allowed, false otherwise.
         */
        public boolean isAllow()
        {
            if (checkAllowBank(left) && checkAllowBank(right))
                return true;
            else
                return false;
        }

        /**
         * Check for the solution state where the puzzle is solved.
         * 
         * @return true if it is solution state, false otherwise.
         */
        public boolean isSolution()
        {
            if (left.isEmpty() && right.contains("W") && right.contains("S") && right.contains("C")
                    && right.contains("F"))
                return true;
            else
                return false;
        }

        /**
         * Transit to a new child State based on the move.
         * 
         * @param move ,Parameter containing the moves (F, FW, FS, FC) to
         *            transit to a new child State.
         * @return State , a new child State based on the transition or null if
         *         the move is not allowed.
         */

        public State transits(String move)
        {
            String nbank;
            TreeSet<String> nleft = new TreeSet<String>();
            TreeSet<String> nright = new TreeSet<String>();

            if (bank.equalsIgnoreCase("left"))
                nbank = "right";
            else
                nbank = "left";

            copylist(right, nright);
            copylist(left, nleft);

            for (int i = 0; i < move.length(); i++)
            {
                String item = move.substring(i, i + 1);
                if (bank.equalsIgnoreCase("left"))
                {
                    if (nleft.remove(item))
                        nright.add(item);
                    else
                        return null; // return null if the move contains
                                     // occupants that are not present.
                }
                else
                {
                    if (nright.remove(item))
                        nleft.add(item);
                    else
                        return null; // return null if the move contains
                                     // occupants that are not present.
                }
            }

            return new State(nbank, nleft, nright);

        }

        /**
         * Method to duplicate/copy a representation of the river bank and its
         * occupants from source to destination.
         */
        private void copylist(TreeSet<String> src, TreeSet<String> dst)
        {
            for (String e : src)
                dst.add(e);
        }

        /**
         * Compares current state with a specific state
         * 
         * @param s The State s to compare with
         * @return true if the current and specified state are the same, false
         *         otherwise
         */
        public boolean compare(State s)
        {
            TreeSet<String> tmp;

            if (!s.getBank().equalsIgnoreCase(bank))
                return false;

            tmp = s.getLeft();
            for (String e : left)
            {
                if (!tmp.contains(e))
                    return false;
            }

            tmp = s.getRight();
            for (String e : right)
            {
                if (!tmp.contains(e))
                    return false;
            }

            return true;
        }

        public String getBank()
        {
            return bank;
        }

        public TreeSet<String> getLeft()
        {
            return left;
        }

        public TreeSet<String> getRight()
        {
            return right;
        }

        @Override
        public String toString()
        {
            StringBuffer ret = new StringBuffer();
            ret.append("{L:");

            for (String e : left)
                ret.append(e);

            ret.append(" ");
            ret.append("R:");

            for (String e : right)
                ret.append(e);

            ret.append("}");
            return ret.toString();
        }

    }

The following shows the code snippet for the Node inner class. It holds a class variable parent that links to its parent node. There is a ArrayList variable holding its children, a variable that holds the State. The isAncestor() method checks whether the current state of the Node has occurred previously along its parent path. To prevent an endless repetitions loop, repeated states along a path is disallowed.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
    /**
     * Private Inner class Node for constructing the State graph
     */
    private class Node
    {
        public Node parent; // Parent of the node
        public State data; // State of the node
        public ArrayList<Node> adjlist; // Children of the node
        public int level; // Depth of the node
        public String move; // The move (transition) that creates the current
                            // node state.

        public Node(State data)
        {
            parent = null;
            this.data = data;
            adjlist = new ArrayList<Node>();
            level = 0;
            move = "";
        }

        /**
         * Checks if a Node that has the same State is an ancestor of the
         * current Node.
         * 
         * @return true if a an ancestor node has the same state, false
         *         otherwise
         */
        public boolean isAncestor()
        {
            Node n = parent;
            boolean ret = false;
            while (n != null)
            {
                if (data.compare(n.data))
                {
                    ret = true;
                    break;
                }

                n = n.parent;
            }

            return ret;
        }

    }

The startBreadthFirstSearch() method in the outer class FarmerWolfCabbageSheep, generates the state space graph using breadth first search. It starts off with a queue containing the initial root node. It process the root, removes it from the queue and adds any valid child nodes into the queue for further processing. When a solution is found, it is added to an ArrayList member variable , solutions. The following shows the code snippet.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
    /**
     * Method to start the creation of the state graph using breadth first
     * search, transiting to allowable states
     */
    public void startBreadthFirstSearch()
    {
        solutions = new ArrayList<Node>(); // Initialize solutions to zero
        TreeSet<String> left = new TreeSet<String>();
        left.add("W");
        left.add("S");
        left.add("C");
        left.add("F");

        State inits = new State("left", left, new TreeSet<String>());
        root = new Node(inits);
        root.level = 0;
        queue.add(root);

        while (!queue.isEmpty())
        {
            Node n = queue.remove(0);
            System.out.println("Processing Level " + n.level + " " + n.data);
            for (String m : moves)
            {

                State s = n.data.transits(m);

                if (s != null && s.isAllow()) // Check if it is allowable state
                {

                    Node child = new Node(s);
                    child.parent = n;
                    child.level = n.level + 1;
                    child.move = m + " moves " + child.data.getBank();

                    // Check that a node doesn't occur already as ancestor to
                    // prevent cycle in the graph
                    if (!child.isAncestor())
                    {
                        n.adjlist.add(child);

                        if (child.data.isSolution() == false)
                        {
                            queue.add(child);
                            System.out.println("Adding state " + child.data);
                        }
                        else
                        {
                            solutions.add(child);
                            System.out.println("Found solution " + child.data);

                        }
                    }

                }

            }

        }
    }

The depth first implementation consists of two methods. The startDepthFirstSearch() method starts the iterative deepening depth first search. It calls the startDFS() method which implements depth first search with a depth limit using recursion. The depth first implementation is independent of the earlier breadth first search method. Both the depth first and breadth first implementation generate the state graph and find solutions independently. The state graph generated and the solutions found though should be the same. The following snippet shows the depth first implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
   /**
     * Method to start the creation of the state graph using iterative depth
     * first search
     */
    public void startDepthFirstSearch()
    {

        int dlimit = 1; // Maximum depth limit
        solutions = new ArrayList<Node>(); // Initialize solutions to zero

        while (solutions.size() == 0 && dlimit <= 10)
        {
            TreeSet<String> left = new TreeSet<String>();
            left.add("W");
            left.add("S");
            left.add("C");
            left.add("F");

            State inits = new State("left", left, new TreeSet<String>());
            root = new Node(inits);
            root.level = 0;

            System.out.println("Starting iterative DFS with depth: " + dlimit);
            startDFS(dlimit, root);
            dlimit++;
        }

    }

    /**
     * Recursive Method to create the state graph using Depth first search (DFS)
     * 
     * @param depth limit of the DFS search
     * @param Node that holds current state
     */
    public void startDFS(int depth, Node r)
    {
        if (depth == 0)
        {
            System.out.println("Maximum depth limit");
            return;
        }

        System.out.println("Processing Level " + r.level + " " + r.data);

        for (String m : moves)
        {
            State s = r.data.transits(m);

            if (s != null && s.isAllow()) // Check if it is allowable state
            {

                Node child = new Node(s);
                child.parent = r;
                child.level = r.level + 1;
                child.move = m + " moves " + child.data.getBank();

                if (!child.isAncestor()) // Check that the node doesn't occur
                                         // already as an ancestor
                {
                    r.adjlist.add(child);

                    if (child.data.isSolution())
                    {// Found a solution

                        solutions.add(child);
                        System.out.println("Found solution " + child.data);
                        return;
                    }
                    else
                    {// Recursive call
                        startDFS(depth - 1, child);
                    }

                }
            }

        }

        // No valid states
        return;

    }

The following snippet shows the main method of the FarmerWolfCabbageSheep class. It creates a new FarmerWolfCabbageSheep object and finds the solutions to the river crossing puzzle using both the breadth first and depth first implementation. The full source code for the class is available at the Github link at the bottom of the article.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
  public static void main(String[] args)
  {
        System.out.println("Solving Wolf, Sheep, Cabbage, Farmer, River Crossing Puzzle\n");
        FarmerWolfCabbageSheep obj = new FarmerWolfCabbageSheep();

        System.out.println("Creating State Graph using Breadth First Search");
        obj.startBreadthFirstSearch();

        System.out.println("\n\nState Graph in Breadth first order");
        obj.printBFSGraph();
        System.out.println("\n\n");

        System.out.println("Solutions to the River Crossing Puzzle BFS");
        obj.printSolution();

        System.out.println("\n\nCreating State Graph using Iterative Depth First Search");
        obj.startDepthFirstSearch();

        System.out.println("\n\nState Graph in Breadth first order");
        obj.printBFSGraph();
        System.out.println("\n\n");

        System.out.println("Solutions to the River Crossing Puzzle Iterative DFS");
        obj.printSolution();

    }

Results of Running the Application

To solve the farmer, wolf, cabbage, sheep, river crossing puzzle, compile the java class and run it.

javac FarmerWolfCabbageSheep.java
java FarmerWolfCabbageSheep

The application will solve the puzzle using breadth first state and then solve it again using iterative deepening depth first search. The solutions and the state graph generated using both methods will be printed out, one after the other. The following screenshot shows the result from the breadth first search, the result from the iterative depth first search is further down and not shown here.

River crossing puzzle solutions
Fig 3. River Crossing Puzzle Solutions

There are a total of 2 solutions to the puzzle. The results show the states represented by curly bracket, the L: indicate left side of the river, while R: indicate right side of the river. C stands for cabbage, S for sheep, F for farmer and W for wolf. The following shows the representation of the initial state, where the cabbage, sheep, farmer and wolf are all on the left side of the river.

{L:CSFW R:}

A state transits to another through a move. Move are represented by -- Members move right->> or -- Members move left->> , where Members are combinations of F, C, S or W. The following shows an example of farmer and sheep moving to the right side of the river.

--FS moves right ->>

The two possible solutions involve a total of 7 moves. The following shows the 2 solutions. Both the breadth first and depth first method will return the same set of solutions.

Solution 1
No. of moves: 7
{L:CFSW R:}--FS moves right->>{L:CW R:FS}--F moves left->>{L:CFW R:S}--FW moves right->>{L:C R:FSW}--FS moves left->>{L:CFS R:W}--FC moves right->>{L:S R:CFW}--F moves left->>{L:FS R:CW}--FS moves right->>{L: R:CFSW}
Solution 2
No. of moves: 7
{L:CFSW R:}--FS moves right->>{L:CW R:FS}--F moves left->>{L:CFW R:S}--FC moves right->>{L:W R:CFS}--FS moves left->>{L:FSW R:C}--FW moves right->>{L:S R:CFW}--F moves left->>{L:FS R:CW}--FS moves right->>{L: R:CFSW}

In the transition listing shown above, solution 1 is as follows:

  • Farmer rows Sheep to right river bank, leaving wolf and cabbage on the left bank.
  • Farmer comes back alone. Sheep is on right bank, wolf and cabbage on left bank.
  • Farmer rows wolf across to the right river bank where sheep is waiting, leaving cabbage on the left bank.
  • Farmer rows sheep back to the left river bank, leaving wolf alone in right bank.
  • Farmer rows cabbage to the right river bank, leaving sheep alone on the left bank.
  • Farmer comes back alone. Sheep is on left bank, wolf and cabbage on right bank.
  • Farmer rows sheep to the right bank where wolf and cabbage are waiting. All of them are now on the right bank.

The alternative solution 2 is as follows:

  • Farmer rows Sheep to right river bank, leaving wolf and cabbage on the left bank.
  • Farmer comes back alone. Sheep is on right bank, wolf and cabbage on left bank.
  • Farmer rows cabbage across to the right bank where sheep is waiting, leaving wolf on the left bank.
  • Farmer rows sheep back to the left bank, leaving cabbage alone in the right bank.
  • Farmer rows wolf to the right bank, leaving sheep alone on the left bank.
  • Farmer comes back alone. Sheep is on left bank, wolf and cabbage on right bank.
  • Farmer rows sheep to the right bank where wolf and cabbage are waiting. All of them are now on the right bank.

Conclusion and Afterthought

Graph search such as breadth first or depth first search are algorithms often used in artificial intelligence to solve problems, such as playing games, path finding etc... The river crossing puzzle is an easy and popular way to learn and apply such graph traversal algorithms.

The full source code for the FarmerWolfCabbageSheep.java is available at the following Github link.
https://github.com/ngchianglin/FarmerWolfSheepCabbageRiverCrossing

If you have any feedback, comments, corrections or suggestions to improve this article. You can reach me via the contact/feedback link at the bottom of the page.

Article last updated on Dec 2017.