From Constraints to Resolution Rules, Part II: chains, braids,
  confluence and T&E
  In this Part II, we apply the general theory developed in Part I to a
detailed analysis of the Constraint Satisfaction Problem (CSP). We show how
specific types of resolution rules can be defined. In particular, we introduce
the general notions of a chain and a braid. As in Part I, these notions are
illustrated in detail with the Sudoku example - a problem known to be
NP-complete and which is therefore typical of a broad class of hard problems.
For Sudoku, we also show how far one can go in 'approximating' a CSP with a
resolution theory and we give an empirical statistical analysis of how the
various puzzles, corresponding to different sets of entries, can be classified
along a natural scale of complexity. For any CSP, we also prove the confluence
property of some Resolution Theories based on braids and we show how it can be
used to define different resolution strategies. Finally, we prove that, in any
CSP, braids have the same solving capacity as Trial-and-Error (T&E) with no
guessing and we comment this result in the Sudoku case.
