Backtracking search

•Variable assignments are commutative 

            [ WA = red then NT = green ] same as

            [ NT = green then WA = red ]

•Depth-first search for CSPs with single-variable assignments is called backtracking search.

•Chooses values for one variable at a time and backtracks when a variable has no legal value.

•Backtracking search is the basic uninformed algorithm for CSPs