Average time analysis of backtracking on random constraint satisfaction problems

A new random CSP (constraint satisfaction problem) model is proposed. By analyzing the expected number of nodes in a search tree, the average running time used by the backtracking algorithm on random constraint satisfaction problems is studied. The results show that the model can generate hard CSP instances, and the expected number of nodes required for finding all solutions or proving that no solution exists becomes exponentially large as the number of variables grows. Therefore, the model can be used to analyze the nature of hard instances and evaluate the performance of CSP algorithms, and hence it helps the researchers to design more efficient algorithms.