You’re playing Scrabble on a graph with limited information about tiles in the queue and with some tiles already placed on the graph. Maximise your total score.
A stupid idea to start: just ignore the vertices with previously placed tiles, always try to find a word in the queue and place it on some free path; if it’s impossible or you have some trash tiles among the letters of that word in the queue, just place them on some vertices. (It wouldn’t get many points, I know.)
This is a nasty challenge problem and I didn’t play around with it, so I don’t know what would work and what wouldn’t. It’d be best if people who tried it wrote their approaches.