I might be a little under-qualified for this question, but here's my take on it:
The function you are looking at is an ellipse elongated along the x-axis, so solutions have a bounded domain in the integers, which is c. We can focus on just one quadrant since an ellipse has 4-fold symmetry, so it makes sense to take x and y to also be both positive, and then extrapolate the other solutions by changing the signs.
If we want to show that we have all integer solutions, we can reduce in a modulus or modulo d and just try all the congruence classes of that form in the integers, as you already have done. Since the domain is bounded, the answer can't be too big. That means we have finitely many integers to try.
This should work for any case just to find the solutions, I don't yet have a more elegant approach (I will edit this post soon). There may be some help in thinking geometrically a bit more.