The aim of this paper was to investigate whether it was possible to induce more internal planning in the four-disk Tower of Hanoi (ToH) in order not only to produce more efficient problem solving but also to make it more resistant to the negative effect of interruption. The theoretical frameworks of soft constraints and the memory for goals model underpinned Experiments 1 and 2. In both experiments, three goal-state access cost conditions were used: high (mouse movements and 2.5-s delay), medium (mouse movements) and low (goal state always available). In Experiment 1, more memory-based planning was induced by the high cost condition, which resulted in fewer moves to solution and the gradual development of an efficient subgoaling strategy, resulting in more perfect solutions. In Experiment 2, the same condition protected performance against a 10-s interruption irrespective of the interrupting task (blank screen, mental arithmetic, or three-disk ToH). The more memory-based planning strategy, induced by high access cost, presumably strengthened participants' goals during planning and problem solving, making them less susceptible to decay and interference from interruption. These novel results are discussed in the context of other recent studies.