understanding constraint satisfaction problem: map coloring algorithm

Question

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.

Answer 1

So after rehashing some college literature (Peter Norvig's Artificial Intelligence: A Modern Approach), it turns out the problem in your hands is the application of Recursive Backtracking as a way to find a solution for the Graph Coloring Problem, which is also called Map Coloring (given its history to solve the problem of minimize colors needed to draw a map). Replacing each country in a map for a node and their borders with edges will give you a graph where we can apply recursive backtracking to find a solution.

Recursive backtracking will descend the graph nodes as a depth-first tree search, checking at each node for whether a color can be used. If not, it tries the next color, if yes, then it tries the next unvisited adjacent node. If for a given node no color satisfies the condition, it will step back (backtrack) and move on to a sibling (or the parent's sibling if no siblings for that node).

So,

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 ... Would it be something like checking the size of the dictionary against the number of states?

Yes and yes. Once the dictionary contains all the nodes of the graph with a color, you'll have a solution.

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?

That pseudocode syntax is confusing but the general idea is that you'll have a way to find out a node of the graph that hasn't been colored yet. One simply way is to return a node from the dictionary that doesn't have a value assigned to it. So if I understand the syntax correctly, var would store a node. VARIABLES[csp] seems to me like a representation of the list of nodes inside your CSP structure.

I'm not sure what the parameters (VARIABLES[csp], assignment, csp) are doing, given my input

The assignment parameter is a dictionary containing the nodes evaluated so far (and the future solution), as mentioned above, and csp is the structure containing a,b and c.

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?

ORDER-DOMAIN-VALUES appears to be a function which will return the ordered set of colors in your CSP structure. The FOR loop will iterate over each color so that they're tested to satisfy the problem at that level.

 if value is consistent with assignment given CONSTRAINT[csp] then

Here, what you're doing is testing the constraint with that value, to ensure it's true. In this case you want to check that any nodes adjacent to that node does not have that color already. If an adjacent node has that color, skip the IF and iterate the for loop to try the next color.

If no adjacent nodes have that color, then enter the IF body and add that node var with color value to the assigment dictionary (I believe {var = value} is a tuple representation, which I would write {var,value}, but oh well). Then call the function recursive backtracking again, recursively. If the recursive call returns non-failure, return its results (it means the solution has been found).

If it returns a failure (meaning, it tried all the colors and all of them happened to be used by another adjacent node), then remove that node ({var,value}) from the assignment (solution) array and move on to the next color. If all colors have been exausted, return failure.