We examined spontaneous external offloading in a study requiring participants to plan the shortest route to connect locations on maps while satisfying ordering constraints. We manipulated map difficulty (low/high) and the possibility for participants to offload cognition by allowing/not allowing them to use a pen during planning (offloading/no offloading). Participants used more types of offloading strategies in the high (vs. low) difficulty maps and showed a better performance in the offloading (vs. no offloading) condition in the high difficulty maps only. However, even in the low difficulty maps, cognition was offloaded, especially when participants solved the high difficulty maps first (perseveration effect). The use of offloading strategies and offloading-supported planning performance were positively related with visual search ability, while performance in the no offloading condition was positively related with spatial working memory. Findings show that offloading strategies are spontaneously deployed in a partly adaptive way in route planning on maps.