1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.