Thank you for sharing this asicsp. I actually made a submission to HN as soon as my post went up, but I think it was pretty late at night for most readers so maybe people missed it.
Just from a quick glance, have you thought about optimising the search algorithm by either using branch and bound, or by doing depth first search?
With a little play I managed to get a 15% performance increase with a few python micro-optimisation tricks:
1. I turned generate_paths() in to agenerator and turned the paths list comprehension in to a generator comprehension so we don't have to build large data-structures containing all paths, just to find a max (since you only need to keep the current max in memory at any given time).
2. I converted PathScore to be a function to avoid a lot of redundant object creations and destructions. This was a major speedup.
3. Finally, I just added __slots__ to the remaining classes, which was a very small win.
First I generate the list of all possible solution sequences (82 in your example) ordering them from shortest to longest.
Then I search for that shorter list in the matrix.
Enjoy: https://gist.github.com/giannitedesco/cc46c347c0337b10e24d00...
Note that the full puzzle isn't really solvable off-line (edit: I mean in a fully general sense) because of the case where you switch from solving one sequence to another and an extra prefix gets added by the game as a punishment!
[0] https://www.reddit.com/r/programming/comments/khgbsc/cyberpw...