How to count cul-de-sacs (aka dead-ends) in a maze using Python?
Problem Statement
I am working on a maze-solving program where I need to count the number of cul-de-sacs, also known as dead-ends. The maze is represented in a way that allows identifying different paths and intersections.
Approaches Tried
- Marking Pathways: Initially, I marked all the nodes between gates and cul-de-sacs with an "X", then labeled all the possible routes from one gate to another. (so far the best one but cannot generalize all the test cases)
- Using Intersection Points: I tried using nodes that have multiple openings as potential dead-end identifiers.
Additional Information
- Breadth-First Search (BFS): I am currently using BFS to traverse all nodes in the maze, but I'm struggling to correctly identify and count dead-ends.
- The maze is represented by 0 and 1 (0 = road and 1 = wall).
Question
What are the possible methods I can use to count the cul-de-sacs in the maze using Python? I am looking for algorithmic suggestions or Python libraries that might simplify this process.
Sample Maze
The maze has 8 accessible cul-de-sacs. The accesses are indicated by triangles
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1],
[0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]]
Solution
Note that the code used to represent your maze does not correspond exactly to your drawing (thick walls in your code, thin walls in the drawing). Nevertheless I had some fun implementing a Maze class that extracts the "thin wall" maze from the "thick wall" data; I added a method to list dead-ends (by which I mean the actual dead-ends, not the entrances you marked on your drawing), a method to cut the maze branch leading to a dead-end, and another to cut all dead-end branches, leaving only (in simple mazes) the correct path.
This doesn't do exactly what you asked (counting entrances), but since your question was a little vague it's the best I could do. You can always build other methods on top of mine to fit your needs.
Edit: I tweaked the code a little. The .trim_maze method now returns a set of dead-end entrances (but the "double" entrance appears only once), and these appear in .show_work_state; the .count_dead_end_entrances computes the number of dead-end paths (so the "double" entrance counts for 2):
from copy import deepcopy
class Maze:
def __init__(self, data):
self.data = data
self.work_data = deepcopy(data)
self.height = len(data) // 2
self.width = len(data[0]) // 2
self.dead_end_entrances = set()
self.exit_dict = {
(-1, 0): 'N',
(1, 0): 'S',
(-0, -1): 'W',
(0, 1): 'E',
}
self.offset_dict = {e: o for o, e in self.exit_dict.items()}
opposite_dict = {
'N': 'S',
'S': 'N',
'W': 'E',
'E': 'W',
}
def node_exits(self, x, y, work=False):
data = self.work_data if work else self.data
if not all((0 <= x <= self.width, 0 <= y <= self.height)):
raise Exception("Out of bounds")
exits = []
for offset, direction in self.exit_dict.items():
if not data[2 * y + 1 + offset[0]][2 * x + 1 + offset[1]]:
exits.append(direction)
return exits
def node_repr(self, x, y, work=False):
ne = self.node_exits(x, y, work)
return(
f' {" | " if "N" in ne else " "} ',
f'{"---" if "W" in ne else " "}{" x " if len(ne) == 1 else " o "}{"---" if "E" in ne else " "}',
f' {" | " if "S" in ne else " "} ')
def node_print(self, x, y, work=False):
print('\n'.join(self.node_repr(x, y, work)))
def __repr__(self, work=False):
return '\n'.join(
'\n'.join(
''.join(
self.node_repr(x, y, work)[i]
for x in range(self.width)
)
for i in range(3)
)
for y in range(self.height)
)
def show_work_state(self):
print(self.__repr__(True))
def dead_ends(self, work=False):
return [(x, y) for x in range(self.width) for y in range(self.height) if len(self.node_exits(x, y, work)) == 1]
def cut_dead_end(self, x, y):
ne = self.node_exits(x, y, work=True)
if len(ne) != 1:
return x, y
self.dead_end_entrances.discard((x, y))
offset = self.offset_dict[ne[0]]
self.work_data[2 * y + 1 + offset[0]][2 * x + 1 + offset[1]] = 1
return self.cut_dead_end(x + offset[1], y + offset[0])
def trim_maze(self):
dead_ends = self.dead_ends(True)
for de in dead_ends:
self.dead_end_entrances.add(self.cut_dead_end(*de))
return self.dead_end_entrances
def count_dead_end_entrances(self):
return sum(
len(self.node_exits(*node)) - len(self.node_exits(*node, True))
for node in self.dead_end_entrances
)
Example:
a = Maze([
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1],
[0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
])
print(a)
o ------ o ------ o ------ o ------ o ------ o ------ o ------ o ------ o x
| | | | |
| | | | |
o ------ o ------ o o o ------ o o ------ o o ------ o
| | | | |
| | | | |
x o ------ o x o ------ o x o ------ o ------ o
| | | | |
| | | | |
o ------ o o ------ o ------ o o ------ o o ------ o o
| | | | |
| | | | |
o ------ o ------ o ------ o ------ o ------ o o ------ o o ------ o
| | | | |
| | | | |
o ------ o o o ------ o o x ------ o ------ o ------ o
| | | | |
| | | | |
o ------ o x o o ------ o o ------ x o ------ o
| | | | |
| | | | |
--- o o ------ o o o ------ x o ------ o o ------ o
| | | | | |
| | | | | |
o o o ------ o o ------ o ------ o ------ o x o
| | | | |
| | | | |
x o ------ o ------ o ------ o x ------ o ------ o ------ o ------ o
|
print(a.dead_ends())
# [(0, 2), (0, 9), (2, 6), (3, 2), (5, 7), (5, 9), (6, 2), (6, 5), (7, 6), (8, 8), (9, 0)]
a.cut_dead_end(0, 2)
a.show_work_state()
o o o o ------ o ------ o ------ o ------ o ------ o x
| | | |
| | | |
o o o o o ------ o o ------ o o ------ o
| | | |
| | | |
o o o x o ------ o x o ------ o ------ o
| | |
| | |
o o o ------ o ------ o o ------ o o ------ o o
| | | | |
| | | | |
o ------ o ------ o ------ o ------ o ------ o o ------ o o ------ o
| | | | |
| | | | |
o ------ o o o ------ o o x ------ o ------ o ------ o
| | | | |
| | | | |
o ------ o x o o ------ o o ------ x o ------ o
| | | | |
| | | | |
--- o o ------ o o o ------ x o ------ o o ------ o
| | | | | |
| | | | | |
o o o ------ o o ------ o ------ o ------ o x o
| | | | |
| | | | |
x o ------ o ------ o ------ o x ------ o ------ o ------ o ------ o
|
print(a.trim_maze())
# {(0, 7), (2, 4), (7, 4), (8, 9), (7, 5), (6, 9), (5, 2)}
a.show_work_state()
o o o o o o o o o o
o o o o o o o o o o
o o o o o ------DEE o o o o
| |
| |
o o o ------ o ------ o o ------ o o o o
| |
| |
o ------ o ------DEE o o o o ------DEE o o
| |
| |
o ------ o o o o o o DEE------ o ------ o
| |
| |
o ------ o o o o o o o o ------ o
| |
| |
---DEE o o o o o o o o ------ o
|
|
o o o o o o o o o o
|
|
o o o o o o DEE------ o ------DEE------ o
|
a.count_dead_end_entrances()
# 8
- WSGIServerException: [Errno 8] nodename nor servname provided, or not known
- Python/Flask Login form throws 500 error on IIS
- Matplotlib plt.show() isn't showing graph
- How to avoid duplicate processing in python API server?
- Extract points/coordinates from a polygon in Shapely
- How do I detect collision in pygame?
- Typehint a method that returns new instance using a superclass classmethod
- How to process requests from multiiple users using ML model and FastAPI?
- How can I clear the interpreter console?
- What are the reasons for the differences in output results when using the groupby function in the Python pandas package?
- How to antialias picture to get rid of the jerkiness in the image
- Is there any difference between list(array) and array.tolist() in Python?
- How to move x-axis on top of the plot in plotnine?
- Pulling Zillow Rent Data from Zillow API
- Safest way to incrementally append to a file?
- Unable to install mysqlclient package on EC2 instance
- FastAPI - How to get app instance inside a router?
- SQLAlchemy: engine, connection and session difference
- Generating binary arrays with alternating values based on change indices in NumPy
- How can i solve this error: ValueError: The feature names should match those that were passed
- 'super' object has no attribute '__sklearn_tags__'
- Python: How to copy all attibutes from base class to derived one
- mitm proxy is closed, but the port is still occupied
- How to find pg_config path
- Why does "pip install" inside Python raise a SyntaxError?
- Plotting a matplotlib pie chart using 2 columns
- ImportError: No module named langchain.llms
- How do I disable the security certificate check in Python requests
- How can I import Psycopg2 into a Lambda Function on AWS?
- Django built in Logout view `Method Not Allowed (GET): /users/logout/`