  We build on a recently proposed method for explaining solutions of constraint
satisfaction problems. An explanation here is a sequence of simple inference
steps, where the simplicity of an inference step is measured by the number and
types of constraints and facts used, and where the sequence explains all
logical consequences of the problem. We build on these formal foundations and
tackle two emerging questions, namely how to generate explanations that are
provably optimal (with respect to the given cost metric) and how to generate
them efficiently. To answer these questions, we develop 1) an implicit hitting
set algorithm for finding optimal unsatisfiable subsets; 2) a method to reduce
multiple calls for (optimal) unsatisfiable subsets to a single call that takes
constraints on the subset into account, and 3) a method for re-using relevant
information over multiple calls to these algorithms. The method is also
applicable to other problems that require finding cost-optimal unsatiable
subsets. We specifically show that this approach can be used to effectively
find sequences of optimal explanation steps for constraint satisfaction
problems like logic grid puzzles.
