<p>Given a (2D) board of quadratic cells (movement allowed between 4-neighbours), many of which are blocked, and given a certain starting position, how can I efficiently detect dead ends, i.e. regions of connected free cells that can be reached from the starting position only through the same connection? Can this be done in O(n)?</p>

<p>Obviously this can also be formulated as a graph problem, but the board shape imposes restrictions (most significantly: no more than 4 edges per vertex) that may lead to a more efficient algorithm.</p>

CC BY-SA 3.0
2011-08-22T08:58:11.623Z
I guess something is missing in the problem formulation. After all, in many cases almost the entire board is a "dead end" in that sense (for example, to reach any position, you must first go left from the starting position).
Jukka Suomela
CC BY-SA 3.0
2011-08-22T09:02:40.477Z
That said, I guess you might be interested in identifying certain [biconnected components](http://en.wikipedia.org/wiki/Biconnected_component) of your graph. For example, if you are given a starting position *and* a goal, then you might want to identify the components that are along the unique path from the start to the goal in the block tree; all biconnected components that are *not* along the path might be considered to be "dead ends".
Jukka Suomela
CC BY-SA 3.0
2011-08-22T13:03:11.923Z
Let $G = (V, E)$ be the graph in question and $s \in V$ be your starting location. Are you trying to find the set of $t \in V$ such that there is a unique $s$-$t$ path?
Tyson Williams
CC BY-SA 3.0
2011-08-22T13:10:31.663Z
@Jukka: I'm primarily interested in finding out whether it's possible to traverse all cells without covering one twice (with some additional constraints), and the presence of two *different* dead ends makes this impossible. Biconnected components are probably the key concept here, so the algorithm on the Wikipedia page should be pretty much what I want. Thanks!
Michael Borgwardt
CC BY-SA 3.0
2011-08-22T13:23:57.413Z
@Michael: If you are interested in traversing all cells exactly once, you are trying to find a [Hamiltonian path](http://en.wikipedia.org/wiki/Hamiltonian_path) in your graph. Hence it sounds like your question could be rephrased as follows: if your graph has the special structure that you described, is there an efficient algorithm for finding Hamiltonian paths. (In the general case, the problem is NP-hard.)
Jukka Suomela
CC BY-SA 3.0
2011-08-22T13:28:48.950Z
For example, this paper might be a good starting point: Umans & Lenhart (1997): "[Hamiltonian cycles in solid grid graphs](http://dx.doi.org/10.1109/SFCS.1997.646138)".
Jukka Suomela
CC BY-SA 3.0
2011-08-22T13:46:35.287Z
@Jukka: Unfortunately there are those additional constraints; namely that traversal always has to continue into the same direction until the next cell in that direction is blocked or already traversed. At the moment, I'm just doing a brute force search and trying to prune the search tree as much as possible.
Michael Borgwardt
CC BY-SA 3.0
2011-08-22T23:03:51.103Z
What are these "additional constraints"?
Tyson Williams
CC BY-SA 3.0
2011-08-23T08:33:24.893Z
I think 3-connected cubic planar graphs can be embedded on a polynomially-sized grid graph (I have a crappy way of doing it from [hexagonal grid drawings](http://www.springerlink.com/content/7140qq8572554620/)). Combining that with the fact that [deciding Hamiltonicity for 3-connected cubic planar graphs is NP-complete](https://www.cs.princeton.edu/courses/archive/spring04/cos423/handouts/the%20planar%20hamiltonian.pdf) makes your problem in the comments NP-hard.
Timothy Sun
CC BY-SA 3.0
2011-08-23T08:38:45.793Z
@Tyson: as I wrote: traversal always has to continue into the same direction as far as possible. Not sure whether/how that can be translated into a pure graph theory problem.
Michael Borgwardt
CC BY-SA 3.0
2011-08-23T12:58:54.483Z
I do not see that addition requirement in your question.
Tyson Williams
<ds.algorithms><graph-algorithms><planar-graphs><board-games>
How to detect dead ends on a board / in a graph?
Michael Borgwardt
# How to detect dead ends on a board / in a graph?

(Asked by: username_0 on 2011-08-22)

Given a (2D) board of quadratic cells (movement allowed between 4-neighbours), many of which are blocked, and given a certain starting position, how can I efficiently detect dead ends, i.e. regions of connected free cells that can be reached from the starting position only through the same connection? Can this be done in O(n)?

Obviously this can also be formulated as a graph problem, but the board shape imposes restrictions (most significantly: no more than 4 edges per vertex) that may lead to a more efficient algorithm.

**Tags:** ds.algorithms, graph-algorithms, planar-graphs, board-games
> **Comments:**
> **username_1**: I guess something is missing in the problem formulation. After all, in many cases almost the entire board is a "dead end" in that sense (for example, to reach any position, you must first go left from the starting position).  
> **username_1**: That said, I guess you might be interested in identifying certain [biconnected components](http://en.wikipedia.org/wiki/Biconnected_component) of your graph. For example, if you are given a starting position *and* a goal, then you might want to identify the components that are along the unique path from the start to the goal in the block tree; all biconnected components that are *not* along the path might be considered to be "dead ends".  
> **username_2**: Let $G = (V, E)$ be the graph in question and $s \in V$ be your starting location. Are you trying to find the set of $t \in V$ such that there is a unique $s$-$t$ path?  
> **username_0**: @Jukka: I'm primarily interested in finding out whether it's possible to traverse all cells without covering one twice (with some additional constraints), and the presence of two *different* dead ends makes this impossible. Biconnected components are probably the key concept here, so the algorithm on the Wikipedia page should be pretty much what I want. Thanks!  
> **username_1**: @Michael: If you are interested in traversing all cells exactly once, you are trying to find a [Hamiltonian path](http://en.wikipedia.org/wiki/Hamiltonian_path) in your graph. Hence it sounds like your question could be rephrased as follows: if your graph has the special structure that you described, is there an efficient algorithm for finding Hamiltonian paths. (In the general case, the problem is NP-hard.)  
> **username_1**: For example, this paper might be a good starting point: Umans & Lenhart (1997): "[Hamiltonian cycles in solid grid graphs](http://dx.doi.org/10.1109/SFCS.1997.646138)".  
> **username_0**: @Jukka: Unfortunately there are those additional constraints; namely that traversal always has to continue into the same direction until the next cell in that direction is blocked or already traversed. At the moment, I'm just doing a brute force search and trying to prune the search tree as much as possible.  
> **username_2**: What are these "additional constraints"?  
> **username_3**: I think 3-connected cubic planar graphs can be embedded on a polynomially-sized grid graph (I have a crappy way of doing it from [hexagonal grid drawings](http://www.springerlink.com/content/7140qq8572554620/)). Combining that with the fact that [deciding Hamiltonicity for 3-connected cubic planar graphs is NP-complete](https://www.cs.princeton.edu/courses/archive/spring04/cos423/handouts/the%20planar%20hamiltonian.pdf) makes your problem in the comments NP-hard.  
> **username_0**: @Tyson: as I wrote: traversal always has to continue into the same direction as far as possible. Not sure whether/how that can be translated into a pure graph theory problem.  
> **username_2**: I do not see that addition requirement in your question.  

---

## 0 answers

