SYSC 2100 Lecture Notes - Lecture 8: Algebraic Expression, Empty String

• School: Carleton University
• Department: Systems and Computer Engineering
• Course: SYSC 2100
• Professor: Jean-Daniel Medjo Me Biomo

Document Summary

Backtracking is a solution strategy that involves both recursion and a sequence of guesses that ultimately lead to a solution. If a guess leads to an impasse, retrace the steps in reverse order, replace that guess with a new one, and try to complete the solution. A recursive algorithm that places a queen in a column. Base case: no more columns to consider nished. If a queen is successfully placed in a current column consider next column. If a queen cannot be placed in current column backtrack placequeens (in currcolumn : integer) // places queens in columns numbered currcolumn through 8. if (currcolumn > 8) the problem is solved else { while (unconsidered squares exist in currcolumn and the problem is unsolved) { Determine the next square in column currcolumn that is not under attack by a queen in an earlier column if (such a square exists) {