# Rooks on a lifeline

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:

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?

-
I may be out of my depth (and breadth?) here, but my understanding is that if you have a (finite) tree then depth-first and breadth-first searches will both eventually visit every node in the tree, just not in the same order. So if depth-first eventually finds everything you're looking for, so will breadth-first, unless you're using those terms with non-standard meanings. Now I'll stop to catch my breadth. – Gerry Myerson Oct 30 '10 at 22:44
That was my first guess too. But the fact that we're adding as many neighbors as possible with each "breadth-first search" step, means that we might commit ourselves to rook placements that would make us miss maximal configurations. If, instead of only adding as many neighbors as possible with each BFS step, we considered all possibilities of adding $\{1,\ldots,n\}$ neighbors (under our constraints), where $n$ is the maximum number of neighbors, then we would definitely find all maximal configurations. So, we're being "greedy" in a sense here. I am worried that this might bite us. – winterstream Oct 31 '10 at 17:37
@winterstream It's been noted in a recent edit that the imageshack link is broken. Could you fix it, please? – Todd Trimble Oct 21 at 14:12