Find all integer solutions to the equation
$$
y(x^2+1)=z^2+1.
$$
There is, for example, an infinite family of solutions $x=u$, $y=(uv\pm1)^2+v^2$, $z=(u^2+1)v \pm u$, $u,v \in {\mathbb Z}$, but there are also solutions outside of this family, e.g. $(x,y,z)=(8,5,18)$ or $(x,y,z)=(12,2,17)$. The question is to describe all integer solutions. Any reasonable description is ok. An algorithm generating all solutions is also ok, provided that it does not involve any search by trial and error (otherwise there is a trivial algorithm that tries all triples $(x,y,z)$ in some order). Using parametric expressions, recurrence relations, or something like ``start with this solution and apply these operations in any order'' (like generating Markov numbers via Markov tree) would be ideal, but more complicated algorithms are also possible. For example, for equation $yz=x^3+1$, there is an obvious algorithm "let $x$ be an arbitrary integer, let $y$ be any divisor of $x^3+1$, and then let $z=(x^3+1)/y$", which I think is acceptable. The equation in question is one of the smallest/simplest ones for which I do not see any reasonable method/algorithm to describe all solutions, hence the question.


Remark: If we define, for any integer $u$, set $S(u)$ as a set of integers $0\leq r < u^2+1$ such that $\frac{r^2+1}{u^2+1}$ is an integer, then all the solutions to the equation are in the form $x=u$, $z=(u^2+1)v \pm r$ and $y=(u^2+1)v^2 \pm 2vr + \frac{r^2+1}{u^2+1}$ for $u,v \in {\mathbb Z}$ and $r \in S(u)$, but we need trial and error to construct set $S(u)$, so I do not think this is an acceptable answer.



Solve in integers: $y(x^2+1)=z^2+1$
The equation says that $z^2 + 1 \equiv 0 \mod (x^2+1)$. For each positive integer $x$, you can enumerate the square roots of $-1$ in the integers mod $x^2+1$ as you remark in your last paragraph. This does not require "trial and error": if you can factor $x^2+1$, you can use the Tonnelli-Shanks algorithm
to find the square roots mod each prime power in the factorization, then put them together using the Chinese Remainder Theorem.


