Need recursive version of Conflict based backjumping
When a conflict is found during a recursive constraint satisfaction search there may be assignments and inferences in the call stack that have no connection to the conflict.  Instead of backtracking through these ineffectual assignments at exponential cost it is better to jump backward over them in the call stack directly to the most recent assignment that made the conflict inevitable.  This is backjumping.

To implement backjumping in the algorithm above, you would do three things:


Make the BACKTRACK function maintain a counter storing the depth of its call stack.
Instead of simply returning failure, have BACKTRACK also return a number representing the stack depth whose BACKTRACK function should resume execution.  This number would be determined by careful examination of the assignments and inferences that led to the conflict.
Have all calls to BACKTRACK at stack depths greater than the returned number simply return the number rather than continue iterating through ORDER-DOMAIN-VALUES.


All the ORDER-DOMAIN-VALUES assignments between the current level and the backjump target level will no longer happen. This gives exponential computational savings with a cost only linear to the size of the backjump.