Constrained Random Verification (CRV) is becoming the mainstream methodology for the functional verification of complex System on Chip (SoC) designs. In CRV, constraint satisfaction problem (CSP) solvers are used to generate the input stimulus required for verification. In order to achieve the verification closure, CRV tools have to produce multiple different solutions, distributed uniformly in the search space. One way to achieve even distribution of solutions is to divide the search space into several clusters and generate solutions from each cluster. Present day partitioning techniques treat the number of cluster as an input which must be given in advance. In this paper, we propose a method for estimating this parameter. The experimental results show that the proposed method helps to find the number of cluster accurately in a very short time.