With a basic understanding of the problem and the expected solution, I start off directly with prototype code - basically creating a barely working prototype to explore possible solutions.
When I'm convinced that I'm on the right track (design-wise), I start adding more functionality.
When I'm at a stage where the solution is passable - I then start writing tests for it. I spend some time working through tests and identifying issues with my solution.
Then I fix the solutions. And clean up the solution.
At this point my test cases should cover most (if not all) of my problem statement, edge cases and expected failures.
When it comes to maintaining the solution, I do start with test cases though. Usually just to ensure that my understanding of the bug or issues is correct. With the expected failure tests, I then work on the fix. And write up any other test cases needed to cover the work.