Naive Recognizer

 static Shape Recognize(IGrid grid) {
    int left = Int32.MaxValue;
    int right = -1;
    int bottom = Int32.MaxValue;
    int top = -1;

    for (int x = 0; x < 8; ++x) {
        for (int y = 0; y < 8; ++y) {
            if (grid.CountBlocksSet(x, x, y, y) == 1) {
                left = Math.Min(left, x);
                right = Math.Max(right, x);
                bottom = Math.Min(bottom, y);
                top = Math.Max(top, y);
            }
        }
    }

    if (right - left == top - bottom) {
        return Shape.Square;
    }

    return Shape.Rectangle;
}