Suggested modification to Bactracking-Search (aima3e Figure 6.5)

[ctjoreilly]

Threee main changes to the pseudocode are suggested:

1. SELECT-UNASSIGNED-VARIABLE, should include the assignment value as an argument, otherwise it has no information on what assignments have already been made.
2. INFERENCE, should include the assignment value as an argument, otherwise it has no information on what assignments have already been made, for e.g. when trying to perform forward checking.
3. The removal of inferences from assignment to be broken into two separate statements that are only to be called if they are relevant.

NOTE: There is some conflation of what an assignment is in the pseudocode with respect to how it was described earlier in the text (end opening paragraph of section 6.1), which relates it solely to a set of variable values. In the pseudocode this is expanded to implicitly include the tracking of domain removals during the INFERENCE() call so that they can be reversed at a later point during backtracking if necessary.

Complete updated pseudocode with changes:

function BACKTRACKING-SEARCH(csp) returns a solution, or failure
 return BACKTRACK({}, csp)

function BACKTRACK(assignment, csp) returns a solution, or failure
 if assignment is complete then return assignment
 var ← SELECT-UNASSIGNED-VARIABLE(assignment, csp)
 for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do
   if value is consistent with assignment then
     add {var = value} to assignment
     inferences ← INFERENCE(csp, assignment, var, value)
     if inferences ≠ failure then
      add inferences to assignment
      result ← BACKTRACK(assignment, csp)
      if result ≠ failure then
       return result
      remove inferences from assignment
     remove {var = value} from assignment
 return failure