Forward checking Are consistency repntccecogrdas Simplest fom of propaiomakes eacharc c 吟玲鸱的 哈哈鸱 NSW SA O可O可O可O可O可O可▣ 可0可可可可0可 0可▣ 可▣ Constraint propagation Arc consistency Simplest form of 哈一玲一哈 哈的一哈 “"””“▣ VTand SAcannot both be bluel Constraint propagation repeatedly enforces constraints locally Arc consistency Arc consistency Simplest fom of 哈哈鸣 哈哈哈 “"。“ “"”"“ If X loses a value.neighbors of X need to be rechecked Arcdetects failureerer than foard checking Forward checking Idea: Keep track of remaining legal values for unassigned variables Terminate search when any variable has no legal values WA NT Q NSW V SA T Chapter 5 25 Constraint propagation Forward checking propagates information from assigned to unassigned vari￾ables, but doesn’t provide early detection for all failures: WA NT Q NSW V SA T NT and SA cannot both be blue! Constraint propagation repeatedly enforces constraints locally Chapter 5 26 Arc consistency Simplest form of propagation makes each arc consistent X → Y is consistent iff for every value x of X there is some allowed y WA NT Q NSW V SA T Chapter 5 27 Arc consistency Simplest form of propagation makes each arc consistent X → Y is consistent iff for every value x of X there is some allowed y WA NT Q NSW V SA T Chapter 5 28 Arc consistency Simplest form of propagation makes each arc consistent X → Y is consistent iff for every value x of X there is some allowed y WA NT Q NSW V SA T If X loses a value, neighbors of X need to be rechecked Chapter 5 29 Arc consistency Simplest form of propagation makes each arc consistent X → Y is consistent iff for every value x of X there is some allowed y WA NT Q NSW V SA T If X loses a value, neighbors of X need to be rechecked Arc consistency detects failure earlier than forward checking Can be run as a preprocessor or after each assignment Chapter 5 30