ABSTRACT
Backtracking is one of the most important algorithm design paradigms. Backtracking methods generally combine recursion and iteration, contain several parameters, and are not usually designed by strictly thinking about problem decomposition and induction. Thus, they appear to be complex to students who study the material for the first time. Fortunately, backtracking algorithms often share a similar structure, which can be exploited in order to ease their design. In any case, students can master backtracking with relative ease by studying examples, and by applying very similar algorithms to different problems. This chapter introduces fundamental concepts related to backtracking, and provides an overview of how it works by examining the simple four-queens puzzleN-queens puzzle. The key to using backtracking effectively is the possibility of efficiently analyzing whether a partial solution satisfies the constraints of the problem. Backtracking is a general strategy for finding solutions to computational problems among a finite set of possibilities.
