Want Higher Scores? That's what "New Game" is for.
If I want a high score, I look at the stats for the upcoming puzzle. I get my best scores from puzzles with less than 400 completion times and a size of 4x5. If I don't see statistics I like, I keep clicking "New Game" until I do.
When that gets boring. I click "New Game" until I see average times above 1000. That's a bit more interesting.