  Backtracking is a basic strategy to solve constraint satisfaction problems
(CSPs). A satisfiable CSP instance is backtrack-free if a solution can be found
without encountering any dead-end during a backtracking search, implying that
the instance is easy to solve. We prove an exact phase transition of
backtrack-free search in some random CSPs, namely in Model RB and in Model RD.
This is the first time an exact phase transition of backtrack-free search can
be identified on some random CSPs. Our technical results also have interesting
implications on the power of greedy algorithms, on the width of random
hypergraphs and on the exact satisfiability threshold of random CSPs.
