Exact phase transition of backtrack-free search with implications on the power of greedy algorithms

Liang Li, Tian Liu, Ke Xu

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…