reading through your code and found the "todo: there must be a better way" comment

Its not much but, you might prefer this way:

     def __str__(self):
         """Return a rectangular string representation of this maze."""
         # find the bounding rectangle
        #rows = [r for r, c in self._spaces]  # todo: there must be a better way
        #cols = [c for r, c in self._spaces]
         rows, cols = zip(*self._spaces) # use zip with '*' unpacking
         row_min, row_max = min(rows), max(rows)
         col_min, col_max = min(cols), max(cols)

         # build the string

If that's what you were referring to here.