We don't have a solution = 我们没有办法, but 我们没有解决 is wrong? Can anyone clarify?
That will be "We didn't solve it."
Personally, I might have said solution as 解决办法, as 办法 equates more to "way/method" in my mind, but Duo is correct here, and 没有办法 is an oft used expression for not being able to do something about a situation.