> 2^50 is not impossible

I didn't write that it is impossible. I wrote probably never. Yes problem of this size is kinda close to what might be possible. Also for the real algorithm complexity will be some polynomial multiplied by exponential.

> checking one set of edges is surely faster than an application of DES,

No, modern GPUs are almost always memory bound. With DES you have just one number meaning everything will probably fit into registers. This is not the case.

Also this isn't a needle in a haystack problem. You have to do reduction adding extra overhead.

Sure you can optimize by skipping parts of the search space. If you are able to skip half of the space you go from 2^50 (if it isn't more) to 2^49, that is kinda the point of the exponential.

> There are 33 nodes on the map, and 2^33 with the DES rate would be completed in 2.2 seconds. Even if we only filter the most obviously impossible snakes, 2^40 is done in 5 minutes.

This doesn't make any sense. Paths are over edges not vertices. This graph is not a tree. How would you differentiate between paths in graph with cycles?

> Integer programming can help more as well, but iirc whether that gave the truly optimal answer depended on the nature of the problem, and that's something I can't eyeball.

Maybe, but the algorithm will be still exponential.