We explore the static behavior of large Boolean networks with methods recasting Boolean regulation into a constraint satisfaction problem. Our analysis includes a modified version of the leaf-removal algorithm as well as belief and survey propagation. This allows to explore the complex solution-space structure of the problem. We find a phase transition from simple to complex regulatory control, and identify relevant regulatory variables which select the fixed points of the network within the global solution space. Some biological implications on Biological Gene Regulatory Networks will be also discussed.