Constraint Satisfaction Problem Graphs

Russell and Norvig's XDC and CSP graphs

• Russell and Norvig have a nice formal way of representing CSProblems.
• They often do, and we avoid the formalism. Formalism aids understanding.
• Often, the formalism can be translated easily into a program.
• X is a set of variables, D is a set of values (domains) those variables contain, and C is a set of constraints.
• In Sudoku, there are 81 Xs, and all 81 Ds are {1,2,3,4,5,6,7,8,9}.
• Let's make the Xs X11,X12..X19, X21...X91,X92...X99.
• There are a whole bunch of constraints formally, but they include X11!=X12...!=X19, X11!=X21...!=X91,and X11!=X33.
• You can make a graph where there are 81 nodes, and the arcs are the != relationship between the two.
• This omits some of the explicit information, but it's really there.