We develop a new robust technique to deduce variance principles for non-integrable discrete systems. To illustrate this technique, we show the existence of a variational principle for graph homomorphisms from $\Z^m$ to a $d$-regular tree. This seems to be the first non-trivial example of a variational principle in a non-integrable model. Instead of relying on integrability, the technique is based on a discrete Kirszbraun theorem and a concentration inequality obtained through the dynamic of the model. As a consequence of this result, we obtain the existence of a continuum of shift-invariant ergodic gradient Gibbs measures for graph homomorphisms from $\Z^m$ to a regular tree.