Check out my bit of Python above - it's easy to do in linear time with dynamic programming. You collect answers to the question "What's the best and worst score I can achive against the i-tile suffix of this puzzle, using a solution starting with x?". So you end up storing four small integers per tile; I actually used a bitmask representing possible scores. Then it's easy to iterate through all the answers that score k, because it's easy to answer the question "Given this prefix (which scores y), can I add tile x to it and achieve my target score?".

You can easily generalize this to any game played on an FSM where transitions score points and you know your opponent's moves in advance.