# CSP Forward checking with n-ary (and binary) constraints

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
return solution

• It might be hard to tell without describing your FC algorithm. Jul 21, 2017 at 12:41
• @YuvalFilmus You're right, I added the pseudo code. Jul 21, 2017 at 13:03

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).

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