Backtracking Algorithms
-
Backtracking algorithms solve constraint satisfaction problems and find a single solution or all solution by using a search tree method to generate permutations of solutions and by exploring only “valid” branches of the search tree, eliminating invalid partial solutions along the way.
-
Examples: N-queens, class scheduling.
N-Queens
-
Suppose you want to put N queens on an N-by-N chessboard in a way that no two queens threaten each other.