L10: Solving Motivation

Question 1

What are the 2 components of constraint solving?

Answer 1

1. Systematic search through an assignment of variables. Extend an assignment to a subset of the variables incrementally. Backtrack if establish that current partial assignment cannot be extended to a solution.
2. Constraint propagation. Deduction based on constraints, current domains. Usually recorded as reductions in domains. After many steps of propagation, each variable domain contains only one value.

Question 2

Is it better to write your own solver?

Answer 2

Speed: while the solver may be specialised to the problem, it is probably not clever enough at exploring the search space.

Simplicity: it is not easy to maintain and document as there is much more code than using a generic solver (e.g. minion)

However, this is not always the case, and some specialised solvers are better than generic solvers (however this requires a lot of effort).

Question 3

Why should we use generic solvers?

Answer 3

Easier to use
- Fewer lines of code
- Easier to maintain

Better to use
- Get strong, efficient constraint reasoning with no effort on your part
- However, with lots of effort and knowledge, it is technically possible to beat a generic solver.

Question 4

What steps would an efficient Sudoku solver take?

Answer 4

• Update sets of values for each cell
• Restore to previous state when search backtracks
• Check for empty sets – no point continuing search

Question 5

What is the advantage of specifying a problem declaratively to a constraint solver?

Answer 5

Much stronger constraint reasoning. It is able to propagate decisions by looking at the implications of an assignment.