Embodiments of a system and method for asynchronous explanation and explanation-based constraint problem solving are generally described herein. In one or more embodiments, an apparatus includes an asynchronous constraint satisfaction problem solving module (ACSPSM), the ACSPSM can be executable by one or more processors. The ACSPSM can be configured to propagate at least one constraint to a plurality of variables by reducing a speculative propagation range of a first variable when a first value in the speculative propagation range of the first variable is in conflict with the constraint. The ACSPSM can be configured to update an explanation for the reduction in the speculative propagation range of the first variable, or backtrack when a choice of a second value for a second variable would result in the speculative propagation range of the first variable becoming empty. The ACSPSM can be multi-threaded.