CSP Forward checking with n-ary (and binary) constraints
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).