  Random constraint satisfaction problems undergo several phase transitions as
the ratio between the number of constraints and the number of variables is
varied. When this ratio exceeds the satisfiability threshold no more solutions
exist; the satisfiable phase, for less constrained problems, is itself divided
in an unclustered regime and a clustered one. In the latter solutions are
grouped in clusters of nearby solutions separated in configuration space from
solutions of other clusters. In addition the rigidity transition signals the
appearance of so-called frozen variables in typical solutions: beyond this
threshold most solutions belong to clusters with an extensive number of
variables taking the same values in all solutions of the cluster. In this paper
we refine the description of this phenomenon by estimating the location of the
freezing transition, corresponding to the disappearance of all unfrozen
solutions (not only typical ones). We also unveil phase transitions for the
existence and uniqueness of locked solutions, in which all variables are
frozen. From a technical point of view we characterize atypical solutions with
a number of frozen variables different from the typical value via a large
deviation study of the dynamics of a stripping process (whitening) that unveils
the frozen variables of a solution, building upon recent works on atypical
trajectories of the bootstrap percolation dynamics. Our results also bear some
relevance from an algorithmic perspective, previous numerical studies having
shown that heuristic algorithms of various kinds usually output unfrozen
solutions.
