We approached this problem by representing it as a Constraint Satisfaction Problem. The variables are the encrypted letters, and their domains are the possible assignments for the letters. The domains begin as the English alphabet. The constraints are the following:
This problem was well-suited to the Constraint Satisfaction Problem structure because, although the state space is large (26! elements) there are many constraints which can be used to effectively reduce it to a much more manageable and computationally feasible size.
Most other work in this area involves using hill-climbing search, genetic algorithms, and other local search techniques. However, these techniques have a number of drawbacks not present in our model. These include:
In summary, our constraint satisfaction method proved to be an extremely effective method; it always returned the correct solution, it found solutions very rapidly, and it scaled surprisingly well to larger inputs.