${\text{Solve for } \forall n \in \mathbb{N}, n \in (1,10^9) \text{ and primes } p \text{ that hold this equation:}}$
$${\sqrt{\lfloor \sqrt{ n^2 }\rfloor+\lfloor \sqrt{ n^2+1 }\rfloor+\lfloor \sqrt{ n^2+2 }\rfloor} = p}$$
Since ${ \forall k \in \mathbb{N}:}$
${0<(\sqrt{k^2+1}-\sqrt{k^2})^2=k^2+1+k^2-2k\sqrt{k^2+1} \lt 1+2k^2-2k\sqrt{k^2}=1}$
$${0<\sqrt{k^2+1}-\sqrt{k^2}<1}$$ $${ \lfloor \sqrt{k^2+1} \rfloor-\lfloor \sqrt{k^2} \rfloor \le 1}$$ $${ \lfloor \sqrt{k^2+1} \rfloor-\lfloor \sqrt{k^2} \rfloor = (0 \lor 1) }$$
${=> (\lfloor \sqrt{ n^2 }\rfloor, \lfloor \sqrt{ n^2+1 }\rfloor,\lfloor \sqrt{ n^2+2 }\rfloor)}$ can either be: ${(n,n,n),(n,n,n+1),(n,n+1,n+1) \text{ or } (n,n+1,n+2)}$
For case ${(n,n,n)}$:
$${p^2=3n => 3|p => p=3, n=3}$$
For case ${(n,n+1,n+2)}$:
$${p^2=3n+3 => 3|p => p=3, n=2}$$
Other two cases are harder to analyse because there numerous solutions since:
If ${p>=5}$, then: ${p=6k+1}$ or ${p=6k-1}$ for some natural number ${k}$
So, in case ${(n,n,n+1)}$: ${p^2=3n+1=3(2k)-1=6k-1}$ and rewriting as:
${(p+1)(p-1)=3n}$ does not make any restrictions except for ${n<=10^9}$.
Similarly for case ${(n,n+1,n+1)}$:
${p^2=3n+2=3(2k-1)+2=6k-1}$ and again, no restrictions whatsoever.
What is the strategy here, in these two harder cases: brute-force or something more clever?
You've made a good start, but there's a simpler way to show there are no solutions for most of your cases. First, your equation is
$$\sqrt{\lfloor\sqrt{n^2}\rfloor+\lfloor\sqrt{n^2+1}\rfloor+\lfloor\sqrt{n^2+2}\rfloor} = p \tag{1}\label{eq1A}$$
With the case of $(n,n,n)$, you've found only $p = 3$ is possible, with $n = 3$ in \eqref{eq1A} confirming this is a solution. Since $\lfloor x \rfloor \le x$, note all of your other cases require at least that
$$\begin{equation}\begin{aligned} n + 1 & \le \sqrt{n^2 + 2} \\ n^2 + 2n + 1 & \le n^2 + 2 \\ 2n & \le 1 \\ n & \le \frac{1}{2} \end{aligned}\end{equation}\tag{2}\label{eq2A}$$
However, since $n \in \mathbb{N}$ and $n \in (1,10^9)$, this is not possible. Thus, there are no additional solutions to \eqref{eq1A}.