Backtracking search Variable assignments are commutative,i.e., [WA=red then NT=green]same as [NT=green then WA=red] Only need to consider assignments to a single variable at each node b=d and there are d"leaves Depth-first search for CSPs with single-variable assignments is called backtracking search Backtracking search is the basic uninformed algorithm for CSPs Can solve n-queens for n25 Chapter 5 12 Backtracking search Variable assignments are commutative, i.e., [WA = red then NT = green] same as [NT = green then WA = red] Only need to consider assignments to a single variable at each node ⇒ b = d and there are dn leaves Depth-first search for CSPs with single-variable assignments is called backtracking search Backtracking search is the basic uninformed algorithm for CSPs Can solve n-queens for n ≈ 25 Chapter 5 12