He can walk in any direction perpendicular to the gradient. The gradient has a zero x-component, and thus any vector with a zero y-component is perpendicular to the gradient as the dot product between the two vectors is zero. That is, he should walk along a line parallel to the x-axis.