How can a blind pixelated 2d mason chip away the entirety of a pixelated 2d rock So the mason is a single pixel and next to him there is a continuous pixelated rock in this 2d pixel space. He can detect rock pixels, he can turn, move forward, and chip away rock he is next to. The mason could, for example, feel his way around the rock and chip away at the rock. However, if he does this, there is a chance he could get lost (say if the rock is thin somewhere), or he could pitch or part of the rock and be left with more rocks, which would make this harder. What algorithm could the blind mason follow that would guarantee the entire rock would be chipped away in the end?
Bonus question: there are more than one mason, but after starting to clear rock they cannot communicate. Can they agree on an algorithm that guarantees the entire rock will be cleared?
 A: As an alternative to depth-first search, assuming the mason starts adjacent to the rock, he can simply move in a square spiral chipping away as necessary until he has made an entire revolution without encountering any rock.  It is interesting to consider saddling the mason with poor memory as well as blindness, if the rock has $n$ pixels, we need $O(n)$ space for depth-first search (consider starting at the middle of a long thin rock with many twists and turns), but the spiral only requires $O(\log{n})$ space since he only needs to remember how far he has travelled and how long ago he last encountered a rock.  (Can we do any better than this?)
A: You can use a depth first search on the rock. If we assume that each pixel of the rock touches another pixel and that the mason can find a first pixel, the rock just becomes a connected graph (the pixels are nodes and edges connect adjacent pixels). If he isn't guaranteed to find the first pixels, he can spiral out until he finds one. If the rock is not connected, then he would have to spiral out indefinitely and find each fragment.
Not sure about multiple masons. Obviously they could agree to let one work while the other does nothing. I believe you could adapt the DFS to prevent them from cutting themselves off and allowing them to work on it simultaneously, but I would have to check that.
