  We show that estimating the complexity (mean and distribution) of the
instances of a fixed size Constraint Satisfaction Problem (CSP) can be very
hard. We deal with the main two aspects of the problem: defining a measure of
complexity and generating random unbiased instances. For the first problem, we
rely on a general framework and a measure of complexity we presented at
CISSE08. For the generation problem, we restrict our analysis to the Sudoku
example and we provide a solution that also explains why it is so difficult.
