← All solutions

This problem can be solved by generating all paths via exhaustive search, with some pruning to discover when a partial path can never lead to a complete path. One particular set of prunings that is sufficient to make the search fast enough is the following (there are probably even simpler ones than these that are sufficient):

• If the distance to the next check-in point is greater than the number of time-steps left to that check-in time, the current partial path can not be extended to a complete path.
• If the set of unvisited cells form two disconnected regions, there are no solutions, the current partial path can not be extended to a complete path.
• A check-point should never be taken ahead of time.