Extending an iterator model for binary trees to backtracking problems
Uta Ziegler · ACM SIGCSE Bulletin · 1998
Rasala [1] developed a design for an object-oriented tree-iterator. This paper extends that design to provide an iterator for backtracking problems. The developed iterator explicitly uses a stack to store partial solutions which must be evaluated and/or extended.The discussed design can be used as a teaching tool for recursion. Students often struggle with this paradigm [2] since - for their taste - too much is happening behind the scenes. Students can explore the explicit stack of the backtracking iterator after each recursion step.The design can be reused for different domains, since it separates domain-specific code from general iterator code. Solutions to the set and the maze problems are shown.