📎

Examples

Example: Map coloring Problem

Coloring 9 territories of Australia {red, green, blue} so that neighbours dont have the same color. (9 regions means 9 contraints).

X={WA, NT, Q, NSW, V, SA, T}X=\{ \text{WA, NT, Q, NSW, V, SA, T}\}

Di={red, green, blue }D_{i}=\{\text {red}, \text { green, blue }\}

C={SA≠WA,SA≠NT,SA≠Q,SA≠NSW,SA≠V,WA≠NT,NT≠Q,Q≠NSW,NSW≠V} \begin{aligned}C=&\{ \text{SA} \neq \text{WA}, \text{SA} \neq \text{NT}, \text{SA} \neq \text{Q}, \text{SA} \neq \text{NSW}, \text{SA} \neq \text{V},\\& \text{WA} \neq\text{NT}, \text{NT}\neq \text{Q}, \text{Q} \neq \text{NSW}, \text{NSW} \neq \text{V}\}\end{aligned} 

SA≠WA\text{SA} \neq \text{WA}is a shortcut for⟨(SA,WA),SA≠WA⟩ \langle(\text{SA}, \text{WA}), \text{SA} \neq \text{WA}\rangle 

Enumeration of all possible value combinations:

{( red, green ),( red, blue ),( green, red ),( green, blue ),( blue , red ),( blue, green )} \{(\text { red, green }),(\text { red, blue }),(\text { green, red }),(\text { green, blue }),(\text { blue }, \text { red }),(\text { blue, green })\} 

Possible solution:

{ WA = red, NT = green, Q = red, NSW = green, V = red, SA = blue, T = red } \{ \text{WA = red, NT = green, Q = red, NSW = green, V = red, SA = blue, T = red}\} 

Constraint Graph:

Example: Scheduling Problem

Scheduling a car assembly in 30 minutes - Every task is a variable XiX_i .

We have 1515 Tasks / Variables

X={ Axle F, Axle B, Wheel RF, Wheel LF, Wheel RB, Wheel LB, Nuts RF,NutsLF,NutsRB,NutsLB,CapRF,CapLF,Cap⁡RB,Cap⁡LB, Inspect } X = \begin{array}{l} \left\{\text { Axle }_{F}, \text { Axle }_{B}, \text { Wheel }_{R F}, \text { Wheel }_{L F}, \text { Wheel }_{R B}, \text { Wheel }_{L B}, \text { Nuts }_{R F},\right.\\ \left.N u t s_{L F}, N u t s_{R B}, N u t s_{L B}, C a p_{R F}, C a p_{L F}, \operatorname{Cap}_{R B}, \operatorname{Cap}_{L B}, \text { Inspect }\right\} \end{array} 

The values viv_i are the time at which a task starts.

Di={1,2,3,…,27}D_{i}=\{1,2,3, \ldots, 27\}

Precedence constraints: (linear constraints)

T1+d1≤T2T_{1}+d_{1} \leq T_{2}when task1 takes d1 minutes to complete and must be executed before task2.

 Axle F+10≤ WheelRF; AxleF+10≤ WheelLF Axle B+10≤ WheelRB; AxleB+10≤ WheelLB WheelRF+1≤NutsRF;NutsRF+2≤CapRF WheelLF+1≤NutsLF;NutsLF+2≤CapLF WheelRB+1≤NutsRB;NutsRB+2≤CapRB WheelLB+1≤NutsLB;NutsLB+2≤CapLB \begin{array}{ll}\text { Axle }_{F}+10 \leq \text { Wheel}_{RF} ; & \text { Axle}_{F}+10 \leq \text { Wheel}_{LF} \\\text { Axle }_{B}+10 \leq \text { Wheel}_{RB} ; & \text { Axle}_{B}+10 \leq \text { Wheel}_{L B}\end{array} \\ \begin{array}{ll} \text { Wheel}_{RF}+1 \leq N u t s_{RF} ; & N u t s_{RF}+2 \leq C a p_{R F} \\ \text { Wheel}_{LF}+1 \leq N u t s_{LF} ; & N u t s_{LF}+2 \leq C a p_{LF} \\ \text { Wheel}_{RB}+1 \leq N u t s_{RB} ; & N u t s_{RB}+2 \leq C a p_{RB} \\ \text { Wheel}_{LB}+1 \leq N u t s_{LB} ; & N u t s_{LB}+2 \leq C a p_{LB} \end{array} 

Also for every single variable XX we add another constraint:

X+dX≤ Inspect X+d_{X} \leq \text { Inspect }

We also have a disjunctive constraint

(AxleF+10≤AxleB)∨(AxleB+10≤AxleF) \left(A x l e_{F}+10 \leq A x l e_{B}\right) \quad \vee\quad\left(A x l e_{B}+10 \leq A x l e_{F}\right) 

Example: Cryptarithmetic CSP

Usually involve higher order constraints.

The goal is to find the right digits so that the sum is arithmetically correct. (no leading zeroes allowed).

TWO+TWOF O U R \begin{array}{r}T W O \\+T W O \\\hline \text{F O U R}\end{array} 

Possible solution: 938+938=1876938 + 938 = 1876

X={F,T,U,W,R,O,X1,X2,X3}X = \{F, T, U, W , R, O, X_1, X_2, X_3\}

D={0,1,2,3,4,5,6,7,8,9}D=\{0,1,2,3,4,5,6,7,8,9\}

Constraints:

Each letter stands for a different digit: Alldiff⁡(F,T,U,W,R,O)\operatorname{Alldiff}(F, T, U, W, R, O)

O+O=R+10⋅X1X1+W+W=U+10⋅X2,X2+T+T=O+10⋅X3,X3=F \begin{array}{l} O+O=R+10 \cdot X_{1} \\ X_{1}+W+W=U+10 \cdot X_{2}, \\ X_{2}+T+T=O+10 \cdot X_{3}, \\ X_{3}=F \end{array} 

The X1,X2,X3X_1, X_2, X_3 variables stand for the digit that gets carried over into the next column by the addition.

All constraints can be shown in a constraint hypergraph :

  1. top square box: alldiff constraint
  1. middle square box: addition constraints (hereCiC_iis used instead ofXiX_ifor the carry digit)
  • How it should be read

    We start off from the top square box. Each edge leads to a letter. Each letter can have a value from our domain under the condition that they are all different.

    Then each of the letters have a sum that sets the carry bit or is influenced by a previous carry bit.

    Each edge just connects variables to their constraints or contraints with eachother.

Example: Sudoku

Variables

X={A1,A2,A3,...,I9}X = \{A_1,A_2, A_3,...,I_9\} - 81 variables / squares.

Constraints

Alldiff(…)\text{Alldiff}(\dots) for every unit (= row, column, box) - 27 constraints.

Solution:

There always is one single solution → inference without search is enough.

ensuring path consistency - reducing domain size for every square to 1.

Higher efficiency by reducing domain in entire units instead of squares.