Consider chess as a constraint satisfaction problem. Is reducing the number of legal moves in Chess in pre-processing a form of constraint propagation?

• True

• False

Answer explanation

Constraint propagation means they consider legal moves only

Can pre-processing solve an entire constrained satisfaction problem?

• True

• False

Answer explanation

For example, there is only one solution that satisfies the constraint.

For a commutative CSP, is it true that the order of the application of moves have an effect of the final outcome of the search?

• True

• False

Answer explanation

The order of applications does not matter for a commutative CSP.

In the four colour problem, we have [x = red then y = green] is equivalent to [x = green and y = red], is this an example of a commutative CSP?

• True

• False

Answer explanation

The order of applications does not matter for a commutative CSP.

Is plain-backtracking an informed search algorithm?

• True

• False

Answer explanation

For it to be informed, it needs to use forward checking and constraint propagation, as well as other heuristics.

Is the most constrained variable the one with the fewest legal values?

• True

• False

Answer explanation

It has the largest number of constraints, so it must have the fewest legal values.

Is checking the least constrained variable an example of the "fail first" heuristic?

• True

• False

Answer explanation

We "fail first" by checking the most constrained variable.

Is a CSP solved if all variables are assigned and all constraints are satisfied?

• True

• False

Answer explanation

This is what it means for a CSP to be solved.

Is selecting a variable with the minimises the legality of moves on other unassigned variables an example of a degree heuristic?

• True

• False

Answer explanation

The degree heuristic means we should look at variables that constraints other unassigned variables the most.

Do we use general purpose algorithms for a constraint satisfaction problem?

• True

• False

Answer explanation

We do use general purpose algorithms.