142 Chapter 5.Constraint Satisfaction Problems function RECURSIVE-BACKTRACKING(assignment,csp)returns a solution,or failure if assignment is complete then return assignment rEC-UMASIONED-VARABLEVARALEnp) arue in ORDE result-RECURSIVE-BACKTRACKING(assignment,csp) SELECT-UNASSIGNEDVARLRE MAIN-VALUESD ment the general-purpose heuristics discussed in the text. WAgroen wehtscxamcgocadanhtatgwpo incremental successor generation described on page 76.Also,it extends the current assign ment to generate a successor,rather than copying it.Because the representation of CSPs is standardized,there is no need to supply BACKTRACKING-SEARCH with a domain-specific initial state,successor function,or goal test.Part of the search tree for the Australia problem is shown in Figure 5.4.where we have assigned variables in the order WA.NT.O. Plain backtracking is an uninformed algorithm in the terminology of Chapter 3,so we do not expect it to be very effective for large problems.The results for some sample problems nCegemeR5omeoeasehennsh are showr142 Chapter 5. Constraint Satisfaction Problems function BACKTRACKING-SEARCH(csp) returns a solution, or failure return RECURSIVE-BACKTRACKING({ }, csp) function RECURSIVE-BACKTRACKING(assignment, csp) returns a solution, or failure if assignment is complete then return assignment var ← SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp], assignment, csp) for each value in ORDER-DOMAIN-VALUES(var , assignment, csp) do if value is consistent with assignment according to CONSTRAINTS[csp] then add {var = value} to assignment result ← RECURSIVE-BACKTRACKING(assignment, csp) if result 6= failure then return result remove {var = value} from assignment return failure Figure 5.3 A simple backtracking algorithm for constraint satisfaction problems. The algorithm is modeled on the recursive depth-first search of Chapter 3. The functions SELECT-UNASSIGNED-VARIABLE and ORDER-DOMAIN-VALUES can be used to imple￾ment the general-purpose heuristics discussed in the text. WA=red WA=green WA=blue WA=red NT=blue WA=red NT=green WA=red NT=green Q=red WA=red NT=green Q=blue Figure 5.4 Part of the search tree generated by simple backtracking for the map-coloring problem in Figure 5.1. incremental successor generation described on page 76. Also, it extends the current assign￾ment to generate a successor, rather than copying it. Because the representation of CSPs is standardized, there is no need to supply BACKTRACKING-SEARCH with a domain-specific initial state, successor function, or goal test. Part of the search tree for the Australia problem is shown in Figure 5.4, where we have assigned variables in the order WA, NT, Q, . . .. Plain backtracking is an uninformed algorithm in the terminology of Chapter 3, so we do not expect it to be very effective for large problems. The results for some sample problems are shown in the first column of Figure 5.5 and confirm our expectations. In Chapter 4 we remedied the poor performance of uninformed search algorithms by supplying them with domain-specific heuristic functions derived from our knowledge of the problem. It turns out that we can solve CSPs efficiently without such domain-specific knowl-