{'fraction_non_alphanumeric': 0.011013215859030838, 'fraction_numerical': 0.0, 'mean_word_length': 5.0198675496688745, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Approximating Solution Probabilities in CSPs

Heuristics for variable and value ordering have proven useful in searching for solutions to constraint satisfaction problem (CSPs). A well-known heuristic guides the search by ordering values based on an estimate of the number of solutions for the problem. In this paper, we introduce a new estimation method that approximates the probability that a given variable/value combination is part of a global solution to a CSP. The method is a natural extension of a method introduced by Dechter and Pearl and we show that it performs better on average. We compare the new method with two existing methods on problems of varying degrees of hardness and show that the approximations for each method become considerably less accurate as problem difficulty increases and as a result the utility of each of the methods as value ordering heuristics decreases significantly.