## 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 (as a new user, I cannot embed images).

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.

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 2010 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 2010 at 17:37

The answer is that you have gotten too greedy! I give my squares coordinates in R^2. Place vertices on the points (z,z) for integers z with absolute value less than 100 and also at (-2,2), (1,2) and (-1,-2). Place edges between (z,z) and (z+1,z+1) for all z and also place edges between ((-2,2) and (0,0)) , ((-1,-2) and (0,0)) , ((-1,-2) and (1,1)), ((2,1) and (0,0)), ((2,1) and (-1,-1)). So 3 non diagonal vertices and 5 non diagonal edges.

Obviously the best we can do is place rooks on the diagonal from (-100,-100) to (100,100).

Now if you start your search at a vertex on the diagonal at or left of (-1,-1) (resp. at or right of (1,1)) then you won't get to the other side of the diagonal since at (-1,-1) (resp (1,1)) you take the edge to (2,1) (resp (-1,-2)) which cuts you off from (2,2) (resp (-2,-2)). That also explains why you can't start at (2,1) or (-1,-2). If you start at (-2,2) you are cut off from both diagonals as you can't cross (-2,-2) and (2,2). But if you start at the origin, you take the edge to (2,2) which shows you can't start at the origin either.

Thus you got too greedy. Close though, and interesting.

-
 I can use some reputation to post a bounty ... this is a very nice construction. – Orange Nov 5 2010 at 8:01 Hope that you got the reputation boost with the acceptance of the answer! Thanks Orange. – winterstream Jan 19 2011 at 10:11