The short version of this question is:
If $G$ is a graph whose nodes are associated with squares of a chessboard, such that no two nodes in the same row or column of the board are adjacent, we want to associate rooks with the vertices of $G$, such that at most one rook appears in each row and column of the chessboard under the constraint that the vertices containing the rooks induce a connected subgraph of $G$ (thus, the rooks are connected to each other with a lifeline, or lifegraph if you want to be specific).
A maximal configuration of rooks is such that no rooks can be added to the chessboard without violating the constraint that each column/row contain only one rook.
Question: A back-tracking depth first search will find all maximal configutions. Will a back-tracking breadth-first search do the same?
Let's consider an $m \times n$ chessboard that will be inhabited by rooks. As is usual with chess problems in graph theory, each square is represented by a vertex: let $v_{s,t}$ represent the square at row $s$ and column $t$ of the board. Now, let $G$ be an arbitrary graph on the set of vertices $V$ that comprise the squares of the chessboard.
We want to fill the chessboard with rooks (said another way: we want to associate rooks with vertices), such that:
- Every row and every column contain at most one rook (more formally, if a rook is associated with a vertex $v_{i,j}$, then no rook will be associated with $v_{i,s}$ for $s \in \{1,\ldots,n\}$) or $v_{t,j}$ for $t \in \{1,\ldots,m\}$),
- The vertices with rooks must induce a connected subgraph of $G$ (hence the reference to a "lifeline" that must connect all rooks).
An example of a chessboard with a single rook (indicated by the black vertex) is shown here
The gray squares show the area covered by the rook - no other rook can be placed on any of the gray squares. Note that I have neglected to color the squares themselves black and white as they should appear on a real chessboard. Edges are indicated by red lines.
Let's consider how we might extend the neighborhood of the black node - call it $v$. There are three vertices adjacent to $v$, but we can only place rooks on at most two of them at a time without violating the constraint that only a single rook cover a given row/column. In fact, there are two ways of placing the rooks, as shown here:
and here (broken link).
A maximal configuration is a valid placement of rooks (according to our constraints) that cannot be extended by the addition of another rook without violating the constraints.
We can enumerate all maximal configurations by performing a back-tracking depth-first search from each node (i.e. each square on the chessboard). With a depth-first search, we only add one rook to the chessboard at a time.
Suppose that we perform a back-tracking breadth-first search instead. At each step, we add as many rooks the board as possible. Of course there possibly are many different ways of adding as many rooks as possible at each step. This is exactly what is done in the two images above: the maximum number of rooks are added in both possible configurations.
Will this strategy also enumerate all maximal configurations?