Cryptoquotes as a CSP

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:

1. No two letters can represent the same letter
2. No two letters can be represented by the same letter
3. All of the decrypted words must be English words
4. Punctuation and word length are invariant

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:

1. The state space has many local minima which can, and often do, trap local search algorithms
2. Local search techniques tend to only find one solution, whereas our algorithm returns all the possible solutions
3. These algorithms fail to take advantage of certain structural patterns inherent in the problem relating word patterns to possible solutions

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.