Rooks on a lifeline - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T15:13:55Z http://mathoverflow.net/feeds/question/44266 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/44266/rooks-on-a-lifeline Rooks on a lifeline winterstream 2010-10-30T18:56:21Z 2010-12-02T06:22:13Z <p>The short version of this question is:</p> <blockquote> <p>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).</p> <p>A <em>maximal</em> 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.</p> <p><em>Question</em>: A back-tracking depth first search will find all maximal configutions. Will a back-tracking breadth-first search do the same?</p> </blockquote> <p>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.</p> <p>We want to fill the chessboard with rooks (said another way: we want to associate rooks with vertices), such that:</p> <ul> <li>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\}$),</li> <li>The vertices with rooks must induce a connected subgraph of $G$ (hence the reference to a "lifeline" that must connect all rooks).</li> </ul> <p>An example of a chessboard with a single rook (indicated by the black vertex) is shown <a href="http://img143.imageshack.us/img143/9262/basicchessboard.png" rel="nofollow">here</a> (as a new user, I cannot embed images).</p> <p>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.</p> <p>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 <a href="http://img185.imageshack.us/img185/6008/option1.png" rel="nofollow">here</a> and <a href="http://img257.imageshack.us/img257/118/option2m.png" rel="nofollow">here</a>.</p> <p>A <em>maximal</em> 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.</p> <p>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.</p> <blockquote> <p>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.</p> <p>Will this strategy also enumerate all maximal configurations?</p> </blockquote> http://mathoverflow.net/questions/44266/rooks-on-a-lifeline/44781#44781 Answer by Orange for Rooks on a lifeline Orange 2010-11-04T04:39:06Z 2010-11-04T04:39:06Z <p>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. </p> <p>Obviously the best we can do is place rooks on the diagonal from (-100,-100) to (100,100).</p> <p>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. </p> <p>Thus you got too greedy. Close though, and interesting. </p>