Quadratic Diophantine equations in two variables seem to be algorithmically solvable usually if not always, though the algorithms seem hairy.
Challenges for correct, elegant, or fast implementations.
A little bit of a challenge in describing the output: a solution could be an infinite set.
The famous quadratic Diophantine equation in 2 variables is the Pell equation.
https://www.alpertron.com.ar/METHODS.HTM describes some solution methods.
Inspired by the incomplete "diophantine" package on hackage.