Search Performance on n queens Standard search A handful of queens Backtracking Solving CSPs with Standard Search Standard Search Children select any value to any variable [O(v*d)] Test complete assignments against CSP Observations 1. The order in which variables are assigned does not change the solution e Many paths denote the same solution(nI), e so expand only one path 2. We can identify a dead end before assigning all variables 9 Extensions to inconsistent partial assignments are always inconsistent So check after each assignment. R. G7 Search Performance on N Queens • Standard Search • Backtracking • A handful of queens 1 2 3 4 Q Q Q Q 8 Solving CSPs with Standard Search Standard Search: • Children select any value to any variable [O(v*d)] • Test complete assignments against CSP Observations: 1. The order in which variables are assigned does not change the solution. Î Many paths denote the same solution (n!), Î so expand only one path. 2. We can identify a dead end before assigning all variables Î Extensions to inconsistent partial assignments are always inconsistent Î So check after each assignment. R, G R, G R, G, B V1 V3 V2