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.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
no subject
Date: 2005-11-06 06:22 pm (UTC)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.