Minimum remaining values Forward checking 哈一哈给一附 嗡 可可口 Degree heuristic Forward checking MRV variable 哈哈 NSW Least constraining value Forward checking 哈哈一哈 WA NT NSW SA 可可可可▣ 1000 queens feasib 高Minimum remaining values Minimum remaining values (MRV): choose the variable with the fewest legal values Chapter 5 19 Degree heuristic Tie-breaker among MRV variables Degree heuristic: choose the variable with the most constraints on remaining variables Chapter 5 20 Least constraining value Given a variable, choose the least constraining value: the one that rules out the fewest values in the remaining variables Allows 1 value for SA Allows 0 values for SA Combining these heuristics makes 1000 queens feasible Chapter 5 21 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 22 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 23 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 24