It's definitely possible to do better: consider

NNNNNNNNNNYYYYYYYYYY
NNNNNNNNNNnYYYYYYYYY

(using a lowercase "n" to mark a choice where you don't score a point)

I think a greedy strategy (if you're forced to put a letter, put that, else put what's above) does pretty well - it may even be optimal. But I haven't proven it yet, and even if it is, it only finds one best solution, not all of them.