3
$\begingroup$

I have implemented my own CSP solver using a Backtracking algorithm. Within the Backtracking algorithm I apply a Forward Checking algorithm (reducing domains of connected, unnasigned variables) that only works with Binary constraints.

The problem I have is that the CSP I try to solve has lots of n-ary constraints, making the FC algorithm mostly redundant.

Is there a way to enhance or replace my FC algorithm, so it works with n-ary constraints. Or is there a "simple" procedure to convert n-ary constraints to binary constraints?

EDIT: Added pseudo code (attempt) of the Forward Checking algorithm:

function ForwardChecking(variable, csp) list of variables with new domains, or failure
    for each constraint in connectedConstraints(variable) do
        if connectedVariable is assigned then
            if constraint is not satisfied then
                return failure
        else 
            for each value in connectedVariable.domain do
                connectedVariable.assign(value)
                if constraint is not satisfied do
                    remove value from connectedVariable.domain
                if connectedVariable.domain.count == 0 then
                    return failure
                add connectedVariable to solution
    return solution
$\endgroup$
  • $\begingroup$ It might be hard to tell without describing your FC algorithm. $\endgroup$ – Yuval Filmus Jul 21 '17 at 12:41
  • 1
    $\begingroup$ @YuvalFilmus You're right, I added the pseudo code. $\endgroup$ – Reinder Kas Jul 21 '17 at 13:03
1
$\begingroup$

Instead of forward checking, try arc consistency. You run arc consistency after every assignment to reduce backtracking.

Another further improvement would be assigning a least constraining value (LCV) to a variable with minimum value in the domain (MRV).

$\endgroup$
1
$\begingroup$

Arc-Consistency algorithm only works on binary constraints.You have to use binary encoding and hidden variable encoding method.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.