Didn't work

n = 129,
Using the recursive version.
Problem : horizontal and diagonal artifacts
I think the problem may be in the order of evaluation - perhaps doing an explicit loop rather than recursive would work better.
This way, I think we're going deep and looking for pieces beyond the edge of current square before doing all the squares at a given level.

Created by Mathematica  (November 15, 2004)