It's been so long since I've played (and even longer since I went for cheats), I can't remember much at all about the difficulty of getting them. I do seem to remember Train being sort of hard. I know Caverns was the last cheat for me to get, though.