SUNY Geneseo Department of Computer Science

Backtracking and the n Queens Problem

Return to List of Lectures

Misc

My hash table solution is available via our “Exercises” page

Final

• Tuesday, May 14, noon
• Comprehensive, but emphasizing material since 2nd hour exam (e.g., backtracking, hashing, probability & expectation, randomized algorithms)
• Designed for 2 hours, you have 3
• Format and rules otherwise similar to hour exams (especially open reference materials)
• Donuts and cider

Questions?

Backtracking

Example: the n queens problem

Design an algorithm to solve n queens

• Basic structure:
  • Backtracking good for finding solutions that consist of parts
  • Recursion adds parts of partial solution

            backtrack( … partialSolution … )
                …
                backtrack( … partialSolution + next part … )

• Our backtracking algorithm to solve n queens, and its correspondence to general backtracking pattern. Note that this assumes 3 other functions
  • placeQueen updates the board with a new queen at row i, column n
  • removeQueen removes a queen at row i, column n
  • threatened determines whether row i, column n is threatened

Next

Randomized algorithms