# understanding constraint satisfaction problem: map coloring algorithm

I am trying to implement this recursive-backtracking function for a constraint satisfaction problem from the given algorithm:

function BACKTRACKING-SEARCH(csp) returns solution/failure
return RECURSIVE-BACKTRACKING({},csp)
function RECURSIVE-BACKTRACKING(assignment,csp) returns soln/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 given CONSTRAINT[csp] then
add {var = value} to assignment
result <- RECURSIVE-BACKTRACKING(assignment, csp)
if result != failure then return result
remove {var = value} from assignment
return failure


The input for csp in BACKTRACKING-SEARCH(csp) is a csp class that contains a) a list of states, b) the list of colors, and c) an ordered dictionary with a state as the key and the value is the list of neighbors of the state that cannot have the same color.

The problem is that I am having a hard time understanding how the algorithm works correctly. If anyone can give me a proper explanation of this algorithm, it would be very much appreciated. Some specific questions I have is:

    if assignment is complete then return assignment


I assume that since assignment is inputted as an empty dictionary {}, that this will return the solution, that is, the dictionary that contains states and their colors. However, I don't understand how I can check if the assignment is complete? Would it be something like checking the size of the dictionary against the number of states?

    var <- SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp)


The input csp class contains a list of states, I assume this could just be var equal to popping off a value in the list? I guess, what's confusing me is I'm not sure what the parameters (VARIABLES[csp], assignment, csp) are doing, given my input.

    for each value in ORDER-DOMAIN-VALUES(var,assignment,csp) do


Again, confused on what the inputs of (var, assignment, csp) are doing exactly. But I assume that it'll go through each value (neighbor) in dictionary of the state?

        if value is consistent with assignment given CONSTRAINT[csp] then
add {var = value} to assignment
result <- RECURSIVE-BACKTRACKING(assignment, csp)
if result != failure then return result
remove {var = value} from assignment


How do I properly check if value is consistent with assignment given constraints[csp]? I assume that constraints should be something that should be apart of my csp class that I haven't implemented yet? I don't understand what this if statement is doing in terms of checking. It would be quite useful if someone can clearly explain this if statement and the body of the if statement in depth.