The visuo-spatial planning process is based on an “opportunistic” combination of heuristics and strategies, carried out in small units during the execution of plans. In order to investigate the functional role of the prefrontal cortex in heuristic switching, 42 healthy controls performed a labyrinth crossing task (the Maps Test). During this computerized version of the Travelling Salesperson Problem, subjects had to decide which order of locations optimizes total travel time and distance. This task was performed with and without 1 Hz repetitive transcranial magnetic stimulation (rTMS), which exerts an inhibitory action on the targeted area, applied during the task over bilateral frontal sites (active stimulation) and parieto-occipital site (sham stimulation). Only repetitive bilateral rTMS over F3 and F4 significantly decreased the number of strategies with changes of heuristics, and increased the number of movements required to solve the task. This behaviour contrasts with the performance of healthy subjects in the planning task, but is consistent with the performance of frontal traumatic brain injury patients. The results indicate that, in a visuo-spatial problem-solving task, the prefrontal cortex is involved in the switching between heuristics during the execution of a plan.