Monoalphabetic substitution cipher solver

A general substitution cipher maps each letter to an arbitrary other letter. The keyspace is 26 factorial - about 4 x 10^26 - so brute force is out. It is nonetheless one of the easiest ciphers to break, because the mapping is consistent and English is highly redundant.

Hill climbing on quadgrams

Score a candidate decryption by the log-probability of its four-letter sequences against English quadgram frequencies. Start from the frequency-matched key, swap two letters at random, keep the swap if the score improves. Repeat a few thousand times, restart from a new random key a few times to escape local maxima, and the correct key emerges. Quadgrams work far better than single-letter frequencies because they capture structure - TION and THAT are enormously more likely than any permutation of the same letters.

• Needs roughly 100+ characters. Below that, several keys score similarly and the climb lands wrong.
• Word boundaries help enormously - if spaces are preserved, single-letter words are A or I, and three-letter words are heavily THE.
• If the climb converges to something almost readable with two letters swapped, that is a local maximum; a restart usually fixes it.