I used to have that view of the world as well, that a lot of the programming I was doing was simultaneously exploring the problem space as well as working towards a solution and thus writing tests (let alone full blown TDD) wouldn't work.

I think that what changed my mind, other than the dubious joy of maintaining my own code a couple of years down the line, was the realisation that while I don't know the solution to the problem yet I do know what each function I'm writing is supposed to do and thats what I should be testing. As a side effect it also meant that the functions I was writing became smaller (easier to test) and it became easier to see what the end solution might look like because I could understand the intermediary steps more easily.

Or to put it another way, I might not know how to write the compiler, say, but I do know that I'll need to start off by reading a line of input and I can test that I'm doing that properly, etc.