In this post we discuss simple breadth-first forward state-space solver for puzzles that can be called “logistics puzzles”. The puzzle about farmer crossing river with cabbage, goat and wolf is probably the most well known example of such puzzles.

## Logistics Puzzles

We start with couple examples. In both of them the goal is to present a plan of crossing a river.

Puzzle 1. [1] A Wolf, A Goat and A Cabbage. A farmer needs to cross a river and to transport a wolf, a goat and a cabbage to the other side in a boat. The boat can carry the farmer and only one item. The following pairs of items can’t be left unattended by the farmer: wolf-goat and goat-cabbage for obvious reasons.

Puzzle 49. [1] Cannibals and Missionaries. Three missionaries and three cannibals must cross a river. Their boat can hold only two people, and it can’t cross the river by itself. If present missionaries can not be outnumbered by cannibals.

The common components of such puzzles are: a list of locations (river sides in the examples above), a list of items to move in between the initial and the goal location and a list of conditions to satisfy while moving. The objective is to plan moves so that the goal state is reached from the initial state while each intermediate step satisfies the conditions.

### World States

We can represent a state of the world in such puzzles by specifying the number of items at each location. If there are items of kind total then the number of items of kind at any location belongs to the set . If there are locations, then the distribution of item across them is described by a point in the set , which is Cartesian product of instances of . Combining all together for all item types we get a complete space . Any world state for such kind of puzzles is a point in .

Such formalization helps to easily enumerate all eligible neighbors of a current state for the purpose of searching a path

in from initial state to the goal state .

### Search Strategy

We will adopt the simplest possible strategy for state-space search. Namely, the algorithm we are going to use is a specialization of Graph-Search algorithm (Figure 3.19 in [2]) with breadth first forward search strategy. Next we will explore Python implementation of this approach and apply it to the two puzzles above.

## Implementation Notes

### Nested Dictionary

Programmatically we can represent a point using, say, nested dictionary. Each item type present in the puzzle will correspond to a key at some level of hierarchy. The dictionary will give a complete world state description, e.g. dct[‘left’][‘goat’] will contain number of goats on left side of the river. Locations and items correspond to different levels of nesting in such dictionary. For the kind of puzzles we are exploring depth 2 of nesting is sufficient (locations and items) but the nested dictionary class can easily describe more complex situations by deeper nesting.

'''Defines class for symmetric nested dictionary treated like a complete tree with methods following depth first traversal. For some additional implementation notes see post http://stackoverflow.com/questions/14692690/access-python-nested-dictionary-items-via-a-list-of-keys ''' import pprint class NestedDict: '''Nested dictionary with the main assumption that it has same keys for all nodes at the same level.''' def __init__(self, dictn=None): '''Initialized empty dictionary and empty list of labels.''' self.dictn = {} if dictn is None else dictn self.labels = [] self.detph = 0 def expand(self, labels, func=lambda: None): '''Given nested list of labels of the form [[L1a, L1b, ...][L2a, ...][L3a, ...]...] creates the tree with leaves created using passed in function. By default leaves values are None. :param labels: nested list of labels. :params func: function to create default leaves. ''' self.dictn = self._expand(labels, func) self.depth = len(labels) self.labels = labels def _expand(self, labels, func): '''Expands dictionary recursively to the next level in the tree depth. :params labels: remaining labels to expand; :params func: function for creating leaves.''' dictn = {} is_leaf = len(labels) == 1 if is_leaf: for label in labels[0]: dictn[label] = func() else: for label in labels[0]: dictn[label] = self._expand(labels[1:], func) return dictn def get_at(self, dpath): '''Returns value given a path as list of labels. :param dpath: list in the form [L1, L2, ...] where Li are labels to follow on corresponding level.''' return reduce(lambda d, k: d[k], dpath, self.dictn) def set_at(self, dpath, value): '''Uses get_at to set value at the path in the tree. Assumes that the tree is already fully expanded. :params dpath: data path in the tree, a list of labels to visit on corresponding level. :params value: value to set on the path.''' self.get_at(dpath[:-1])[dpath[-1]] = value def get_as_str(self): return pprint.pformat(self.dictn, indent=1, width=800)

### World State

To describe world state we subclass nested dictionary and end up with a more specialized class:

'''Logistics puzzle state.''' import copy import nested_dict class State(nested_dict.NestedDict): '''A 'template' state of a logistics puzzle world. The only assumption is that any state is a subset of Cartesian product of state components (which is always true but is highly redundant if the valid subset is small).''' def __init__(self, labels, state_values): '''World state described by nested dictionary. :params labels: labels, a list of lists; e.g. the first one is locations e.g. ['left', 'right'] second one is item label e.g. ['goat', 'wolf', etc]. :params values: list of pairs, e.g. [['left', 'goat'], 1] which corresponds to one goat on left bank of river. ''' nested_dict.NestedDict.__init__(self) self.expand(labels, func=lambda: 0) for item, item_value in state_values: self.set_at(item, item_value) self.prev_state = None def get_neighbor(self): '''Returns deep copy of self, sets self as predecessor.''' state_candidate = copy.deepcopy(self) state_candidate.prev_state = self return state_candidate def enumerate_neighbors(self): return [] def is_valid(self): return True def equals(self, other): '''The danger of strings comparison is that order used for formatting string representation may vary.''' return self.get_as_str() == other.get_as_str() def get_path(self, prefix=[]): ''' Returns list of the states visited on the way to the current. Used to print out solution.''' prefix.append(self.get_as_str()) if not self.prev_state is None: self.prev_state.get_path(prefix)

As an example of specialization of world state, consider PuzzleState class for cannibals and missionaries.

import state class PuzzleState(state.State): '''Defines state in the search graph for missionaries and cannibals puzzle.''' locations = ['left', 'right'] items = ['boat', 'missionaries', 'cannibals'] labels = [locations, items] boat_capacity = 2 def __init__(self, state_values): state.State.__init__(self, PuzzleState.labels, state_values) def side_is_valid(self, side): '''Returns true is on the given side of the river the number of cannibals does not exceed number of missionaries.''' return self.dictn[side]['missionaries'] >= self.dictn[side]['cannibals'] \ or self.dictn[side]['missionaries'] == 0 def is_valid(self): '''True of the state is valid, i.e. missionaries can't be eaten.''' return self.side_is_valid('left') and self.side_is_valid('right') def boat_location_and_destinations(self): '''Returns current location of boat and possible destinations for it.''' destinations = [] location = None for loc in PuzzleState.locations: if self.dictn[loc]['boat'] == 1: location = loc else: destinations.append(loc) return location, destinations def enumerate_neighbors(self): '''Returns list of admissible states directly reachable from the current state (self).''' neighbors = [] location, destinations = self.boat_location_and_destinations() neighbors = [] location, destinations = self.boat_location_and_destinations() for dest in destinations: for mm in range(self.dictn[location]['missionaries'] + 1): for cc in range(self.dictn[location]['cannibals'] + 1): n_moved = cc + mm if n_moved > PuzzleState.boat_capacity or n_moved == 0: continue state_candidate = self.get_neighbor() state_candidate.move(location, dest, "cannibals", cc) state_candidate.move(location, dest, "missionaries", mm) state_candidate.move(location, dest, "boat", 1) if state_candidate.is_valid(): neighbors.append(state_candidate) return neighbors def move(self, from_location, to_location, item, n_items): '''Moves n_items of kind item between two locations.''' self.dictn[from_location][item] -= n_items self.dictn[to_location][item] += n_items

We may consider introduction of another intermediate class for river crossing puzzles. Then functions move and boat_location_and_destinations will be factored out to that new class.

### Solver

The solver below uses string representation of a state to keep track of the visited states and assumes that states implement an appropriate get_as_str() method.

class BreadthFirstForward: def __init__(self, initial, goal): ''' Saves the initial state and the goal state as an instance variables. Initializes the internal bookkeeping: lists of visited and fringe states.''' self.initial = initial self.goal = goal self.visited = [initial.get_as_str()] self.fringe = [self.initial] def run(self): '''Implements the simplest version of breadth first search using FIFO queue for the fringe states.''' while self.fringe: state = self.fringe[0] if state.equals(self.goal): return state self.fringe = self.fringe[1:] new_states = state.enumerate_neighbors() for new_state in new_states: state_hash = new_state.get_as_str() if state_hash in self.visited: continue self.visited.append(state_hash) self.fringe.append(new_state) def solve_breadth_first(start, goal): '''A wrapper to create solver, run it and print result to console.''' slv = BreadthFirstForward(start, goal) solution = slv.run() if not solution is None: solution_str = [] solution.get_path(solution_str) for line in solution_str: print line else: print "No solution."

An output for the missionaries and cannibals puzzle looks like this:

import solver missionaries = [['left', 'missionaries'], 3] cannibals = [['left', 'cannibals'], 3] boat = [['left', 'boat'], 1] start = PuzzleState([missionaries, cannibals, boat]) missionaries = [['right', 'missionaries'], 3] cannibals = [['right', 'cannibals'], 3] boat = [['right', 'boat'], 1] goal = PuzzleState([missionaries, cannibals, boat]) solver.solve_breadth_first(start, goal) {'left': {'boat': 0, 'cannibals': 0, 'missionaries': 0}, 'right': {'boat': 1, 'cannibals': 3, 'missionaries': 3}} {'left': {'boat': 1, 'cannibals': 2, 'missionaries': 0}, 'right': {'boat': 0, 'cannibals': 1, 'missionaries': 3}} {'left': {'boat': 0, 'cannibals': 1, 'missionaries': 0}, 'right': {'boat': 1, 'cannibals': 2, 'missionaries': 3}} {'left': {'boat': 1, 'cannibals': 3, 'missionaries': 0}, 'right': {'boat': 0, 'cannibals': 0, 'missionaries': 3}} {'left': {'boat': 0, 'cannibals': 2, 'missionaries': 0}, 'right': {'boat': 1, 'cannibals': 1, 'missionaries': 3}} {'left': {'boat': 1, 'cannibals': 2, 'missionaries': 2}, 'right': {'boat': 0, 'cannibals': 1, 'missionaries': 1}} {'left': {'boat': 0, 'cannibals': 1, 'missionaries': 1}, 'right': {'boat': 1, 'cannibals': 2, 'missionaries': 2}} {'left': {'boat': 1, 'cannibals': 1, 'missionaries': 3}, 'right': {'boat': 0, 'cannibals': 2, 'missionaries': 0}} {'left': {'boat': 0, 'cannibals': 0, 'missionaries': 3}, 'right': {'boat': 1, 'cannibals': 3, 'missionaries': 0}} {'left': {'boat': 1, 'cannibals': 2, 'missionaries': 3}, 'right': {'boat': 0, 'cannibals': 1, 'missionaries': 0}} {'left': {'boat': 0, 'cannibals': 1, 'missionaries': 3}, 'right': {'boat': 1, 'cannibals': 2, 'missionaries': 0}} {'left': {'boat': 1, 'cannibals': 3, 'missionaries': 3}, 'right': {'boat': 0, 'cannibals': 0, 'missionaries': 0}}

There is a potential caveat with using string to represent state in keeping track of visited states. We need to make sure the nested dictionary is traversed in the same order each time by the pprint function pformat. Here we rely on the pprint module implementation and do not provide any additional guarantees. If the assumption fails, the search will not fail but will become more expensive as we will be visiting same state more than once. Eventually the search will return a solution if it exists but it may differ from the breadth first search solution.

Finally, it is obvious that reverting initial and goal state will turn the algorithm into a backward search.

## Discussion

It might be an interesting exercise (for which we may have a separate post in the future) to build an automated puzzle generator. It is relatively easy to come up with a generator and parser of first order logic rules describing valid states. Automated class generation for such rules could be also not so difficult to implement. The main challenge would be conversion of abstract items, locations and transitions into human readable puzzle fiction. Even without going that far, the framework we outlined here allows to test simple variations to the existing puzzles, say adding more items and locations (e.g. an island where items can be “parked” temporarily). We can also add item conditions: a perishable item left on initial side of a river for longer than certain number of moves is a loss and leads to an invalid state of the world. That will increase depth of the nested dictionary to three (locations, items, item conditions).

## References

[1] A. Levitin, M. Levitin, Algorithmic Puzzles, Oxford University Press, 2011, 257 pages.

[2] S. Russel, P. Norvig, Artificial Intelligence, Modern Approach, Second Edition, Prentice Hall, 2003, 1081 pages.

[3] More river crossing puzzles https://justpuzzles.wordpress.com/2011/02/16/river-crossing-1/