[image source: http://xkcd.com/1134]

- What states exist and how do we encode them?
- What operators can we define to transition between states?
- What control strategy do we use to find a solution?

Let \(Items\) be the set of objects in our search problem: \[ Items = \{Farmer, Wolf, Goat, Cabbage\} \]

We encode the state as a pair of sets \((L, R)\), with \(L, R \subseteq Items\), representing the position of the farmer, animals and vegetable on the two banks of the river.

The initial state is \(s_0 = (\{Farmer, Wolf, Goat, Cabbage\}, \emptyset)\).

The goal state is \(s_n = (\emptyset, \{Farmer, Wolf, Goat, Cabbage\})\).

Note that we do not explicitly encode the location of the boat (the farmer always moves with the boat)

In [1]:

```
farmer = 'Farmer'
wolf = 'Wolf'
goat = 'Goat'
cabbage = 'Cabbage'
initial_state = ({farmer, wolf, goat, cabbage}, set())
goal_state = (set(), {farmer, wolf, goat, cabbage})
```

We have two subsets of a total of four items, i.e., \(2^4 \cdot 2^4 = 256\) possible combinations.

Aside: This is a very small search space -- the number of possible chess board configurations is \(O(10^{43})\) [1]

[1] Claude Shannon (1950). "Programming a Computer for Playing Chess". *Philosophical Magazine* **41** (314).

In [2]:

```
def powerset(s):
from itertools import chain, combinations
return [set(x)
for x in chain.from_iterable(
combinations(s, r) for r in range(len(s) +1))]
items = {farmer, wolf, goat, cabbage}
subset_pairs = [(L, R) for L in powerset(items) for R in powerset(items)]
len(subset_pairs)
```

Out[2]:

However, most of the 256 combinations do not represent valid states. Two implicit constraints:

- Everyone must be at one bank of the river at all times: \[ L \cup R = \{Farmer, Wolf, Goat, Cabbage\} \]
- Nobody can be at both banks at the same time: \[ L \cap R = \emptyset \]

(our state is actually a partition of a 4-element set into two disjoint subsets)

This leaves \(2\cdot S(4,2) + 2 = 16\) possible states.

\(S(n, k)\) is a Stirling number of the second kind, giving the number of ways that a set with \(n\) elements can be partitioned into \(k\) non-empty subsets.

In [3]:

```
[(L, R)
for (L, R) in subset_pairs
if L.union(R) == items and L.intersection(R) == set()]
```

Out[3]:

Additional explicit constraint given in the problem description:

- The wolf cannot be left alone with the goat, nor the goat with the cabbage.

We define a function that detects valid states.

In [4]:

```
def is_valid_state(state):
"""A state is a 2-tuple of sets (L, R). It is valid if it satisfies our three constraints."""
# first constraint
if state[0].union(state[1]) != {farmer, wolf, goat, cabbage}:
return False
# second constraint
if state[0].intersection(state[1]) != set():
return False
# third constraint
for bank in state:
if farmer not in bank and (
(goat in bank and wolf in bank) or
(goat in bank and cabbage in bank)):
return False
return True
```

In [5]:

```
[state for state in subset_pairs if is_valid_state(state)]
```

Out[5]:

The set of operators comprises the farmer crossing the river with at most one item, in either direction.

Each operator is a pair \((Boat, d)\), where \[Boat \in \{\{Farmer\}, \{Farmer, Cabbage\}, \{Farmer, Goat\}, \{Farmer, Wolf\}\}\] and \[d \in \{left, right\}\]

Hence, we have \(8\) operators for this problem.

In [6]:

```
operators = {(items, direction)
for items in {(farmer, wolf),
(farmer, goat),
(farmer, cabbage),
(farmer,)} # the farmer can cross alone.
for direction in {'left', 'right'}}
operators
```

Out[6]:

An operator generates a new state by moving elements from one set to the other. For a state \(s=(L,R)\) and an operator \(o=(Boat,d)\), we let

\[make\_move( s, o ) = \left\{ \begin{array}((L \setminus Boat, R \cup Boat) & \text{if}~~d = right \\ (L \cup Boat, R \setminus Boat) & \text{if}~~d = left \end{array} \right. \]

In [7]:

```
def make_move(state, operator):
"""We apply an operator by removing elements from one set
and adding them to the other."""
left, right = state
items, direction = operator
if direction == 'right':
return (left.difference(items), right.union(items))
else:
return (left.union(items), right.difference(items))
```

We define the conditions under which an operator \(o=(Boat,d)\) can be applied to a state \(s=(L,R)\):

- If \(d = right\), \(Boat \subseteq L\) must hold
- otherwise, \(Boat \subseteq R\)

I.e., we can only move items that are actually there.

In [8]:

```
def is_valid_move(state, operator):
"""An operator can be applied to a state if everyone crossing
the river is on the correct bank."""
items, direction = operator
# the river bank where the move starts
from_bank = 0 if direction == 'right' else 1
return state[from_bank].issuperset(items)
```

Given a starting state, we can enumerate all valid successor states using the operators.

In [9]:

```
def valid_successors(state):
succ = []
for op in operators:
next_state = make_move(state, op)
if is_valid_move(state, op) and is_valid_state(next_state):
succ.append((next_state, op))
return succ
```

As a control strategy, we choose breadth-first search.

Does our encoding of state and operators by itself guarantee a systematic search?

In [10]:

```
# represent partial solutions as a tuple of visited states,
# and list of operators applied so far
queue = [([initial_state], [])]
# the solutions we find go here
solutions = []
while len(queue) > 0:
# do BFS: take first element from queue:
visited, oplist = queue.pop(0)
# last visited is current state:
current_state = visited[-1]
for new_state, op in valid_successors(current_state):
new_visited = visited + [new_state]
new_oplist = oplist + [op]
if new_state == goal_state:
solutions.append((new_visited, new_oplist))
elif new_state not in visited:
queue.append((new_visited, new_oplist))
```

In [11]:

```
import pandas as pd
from StringIO import StringIO
def print_solution_table(solution):
sol_buffer = StringIO()
def print_row(state, move):
sol_buffer.write(", ".join(state[0])+'\t'+", ".join(state[1])+'\t')
if move:
sol_buffer.write(str(" and ".join(move[0])) + ' to the ' + str(move[1]) + '\n')
states, operators = solution
for state, move in zip(states, operators):
print_row(state, move)
last_state = states[-1]
print_row(last_state, None)
sol_buffer.seek(0)
df = pd.read_table(sol_buffer, names=['Left bank', 'Right bank', 'move']).replace(float("NaN"), "")
return df
```

In [12]:

```
len(solutions)
```

Out[12]:

In [13]:

```
print_solution_table(solutions[0])
```

Out[13]:

In [14]:

```
print_solution_table(solutions[1])
```

Out[14]: