This problem is as hard as factoring. Factoring has been intensely studied, and it is believed that there is unlikely to be an efficient algorithm for factoring. It follows that there is unlikely to be an efficient algorithm for your problem, either.
Justification: If there was an efficient algorithm for your problem, we could use it to factor $N$. In particular, since $N+A^2=B^2$, we have $N=(B-A)(B+A)$, so with high probability we will have found a non-trivial factor for $N$.
This reduction establishes that there is unlikely to be any simple and efficient algorithm for your problem. If there were a simple and efficient algorithm for your problem, there would be a simple and efficient algorithm for factoring, and we probably would have found it already.
The basic fact -- if we can write $N$ as a difference of squares we can use it to factor $N$ -- is well known to researchers working on factoring. For instance, it is used in Fermat's factoring method, the quadratic sieve, and other factoring methods. So, you are heading down a well-trodden path, one that factoring researchers have already spent a lot of time on. I don't think it's a promising direction. Some new idea would be needed. Progress on factoring has come largely from deep number-theoretic insights; this kind of very simple algebraic fact doesn't seem to be enough.