A CSP is k-consistent if, for any set of k - 1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any _k_th variable. A CSP is strongly k-consistent if it is k-consistent and is also (k - 1)-consistent, (k - 2)-consistent, ... all the way down to 1-consistent.
From the definition above, I do not understand how a CSP can just be k-consistent but not strongly k-consistent.
If the CSP is k-consistent, doesn't it necessarily have to be k-1-consistent too? If not, could you provide an example?
Consider, for example, the problem of completing a partially-filled-in Latin square.
Any consistent grid with just one blank cell can always be completed. Since only one cell is blank, the row that cell is in must be missing exactly one digit (if it's missing more than one, then some other digit must appear twice in that row by the pigeonhole principle, making the partial grid inconsistent). The same applies for the blank cell's column, and in fact it must be the same digit missing (proof is left as an exercise to the reader; hint: count the occurrences of each digit). It follows that this missing digit can be consistently assigned to that blank cell. So the CSP of n×n Latin squares is n2-consistent.
On the other hand, there are lots of consistent partial grids (i.e. grids whose filled-in digits haven't broken any of the rules so far) which cannot be filled in without breaking any rules, for example the following 2×2 grid cannot be made into a Latin square by filling in the blanks, because each of the blanks has no consistent assignment:
1 .
. 2
So this is a consistent set of assignments to two variables with no consistent assignment to a third variable, meaning that the CSP of 2×2 Latin squares is not 3-consistent; we already showed that it is 4-consistent, but now we have shown it is not strongly 4-consistent.