There is a deterministic algorithm for finding solutions to diagonal equations of degree less than or equal to the number of variables. See Christiaan van de Woestijne's thesis.
(A solution of your example equation can be found much more simply, however: try small integers, not necessarily distinct... . And for quadratic forms, the other solutions can be found by drawing lines through the point and intersecting with the quadric hypersurface: there will either be one more intersection point, or a whole line of points.)