a backtracking algorithm maintaining strong k-consistency would not encounter a dead-end until xn k    is instantiated. Then it would find that the subproWem of xn  k is not strongly k-consistent. Thus, the algorithm will backtrack before it reaches the second pigeon-hole subproblem. It will explore π nodes at level n - k     of the search tree and thus take an exponential number of steps to find the problem is insoluble. CBJ does not encounter a dead-end at the level of x n k   and it continues to the second pigeon-hole problem. Eventually it will find the second-pigeon hole problem is insoluble and backjump to the root of the search tree. The total number of nodes explored is bounded by a constant, k , for a fixed k. Therefore, CBJ can be exponentially better than an algorithm 0 k maintaining strong k-consistency.

h l

$\hbar$. 
$$h_{\mathrm{i}}$$
$$k\qquad k$$
$$x_{n}\quad k$$
k

$$k$$

-
k

$\downarrow$ . 
$\downarrow$ . 
$\frac{1}{2}$  . 

l

$\frac{1}{6}$ . 
$$k$$
$\downarrow$ . 
$ n$. 

$\frac{1}{6}$. 
h ordering y , . . , Yk, x , . . , xn   ; Yk