What is the complexity of finding of all paths

Question

There is a map, consisting of hexagonal fields. On this map we have a pawn. He cannot visit any location twice. What is the complexity of an algorithm that's going to find ALL possible paths without repetitions? (basically finding all possible paths, not necessary going through all fields, as it's possible the pawn will run himself into a corner, he goes as long as ha can move).

Answer 1

The complexity is O(5ⁿ).

• From every field except the first one, at most 5 moves are possible.
• If the pawn is moved to a field, it creates a unique path (no checking necessary, whether the path is already visited).
• Keeping track of which fields can be visited from any given field can be done in O(1).

Lower bounds might exist depending on the shape of the map.