Node and Arc Consistency

• You can have unary constraints on a variable (node in a graph).
• It's node consistent if it satisfies it's unary constraints.
• An example is the given cells in Sudoku. Those values can be treated as unary constraints, and so the initial puzzle is node consistent.
• It's interesting that all n-ary constraints can be made into binary ones.
• A variable is arc consistent if all of the binary constraints are satisfied.
• In general, you can reduce the domain sizes by applying node consistency and arc consistency.
• Note that there are special CSP solving systems made to help with these problems.