  We explore the problem of step-wise explaining how to solve constraint
satisfaction problems, with a use case on logic grid puzzles. More
specifically, we study the problem of explaining the inference steps that one
can take during propagation, in a way that is easy to interpret for a person.
Thereby, we aim to give the constraint solver explainable agency, which can
help in building trust in the solver by being able to understand and even learn
from the explanations. The main challenge is that of finding a sequence of
simple explanations, where each explanation should aim to be as cognitively
easy as possible for a human to verify and understand. This contrasts with the
arbitrary combination of facts and constraints that the solver may use when
propagating. We propose the use of a cost function to quantify how simple an
individual explanation of an inference step is, and identify the
explanation-production problem of finding the best sequence of explanations of
a CSP. Our approach is agnostic of the underlying constraint propagation
mechanisms, and can provide explanations even for inference steps resulting
from combinations of constraints. In case multiple constraints are involved, we
also develop a mechanism that allows to break the most difficult steps up and
thus gives the user the ability to zoom in on specific parts of the
explanation. Our proposed algorithm iteratively constructs the explanation
sequence by using an optimistic estimate of the cost function to guide the
search for the best explanation at each step. Our experiments on logic grid
puzzles show the feasibility of the approach in terms of the quality of the
individual explanations and the resulting explanation sequences obtained.
