Solving Headline Puzzles using just one of the headlines.
I've had some success solving headline puzzles by using just one of the headlines to get the key. As an example, here's headline number two of the March 2009 puzzle from the Phoenix Society Puzzles .
Headline #2
KXHDURK DHXXZ HR XIASOI QGJIA G QHCC HR MGRJA
Solving this, we get:
Growing worry on rescue takes a toll on banks.
with the encrypting alphabet:
abcdefghijklmnopqrstuvwxyz
GMS-I-K-U-JC-RH--XAQO-D-Z-
(The 10 dashes represent the 10 missing letters)
Given this encrypting alphabet how do we find the key to the puzzle? We use a computer to search through a list of possible key words for a key that is consistent with the encrypting alphabet for some hat length. For every word on the list the computer program loops through a range of possible hat lengths (I used lengths 5 to 10 in this particular case) testing each length for consistency. Of course, given a possible key and a possible hat length you don't know the order in which the columns are taken off from the transposition block, but you do at least know what the columns are. Just knowing the columns is enough to do quite a lot of consistency checking. Here are 3 types of consistency checks:
Type (1): if the encrypting alphabet tells you that plaintext 'a' is encrypted as ciphertext G, and neither 'a' nor 'g' is at the bottom of their respective columns then the letter following 'a' in the column that contains 'a' must be encrypted as the letter following 'g' in the column that contains 'g'.
If one of the letters is at the bottom of a column, you can still do other types of consistency checks.
Type (2): if 'a' was not at the bottom of its column, but 'g' was, then the letter following 'a' in the column that contains 'a' must be encrypted by one of the letters in the top row of the transposition block, excluding the top of the column containing 'g'.
Type (3): if 'a' was at the bottom of its column, but 'g' was not , then the letter following 'g' in the column that contains 'g' must be the encryption of one of the letters in the top row of the transposition block, excluding the top of the column containing 'a'.
In the particular case of the encrypting alphabet for headline 2 above, suppose we are trying DECLIVOUS as a possible key and 8 as a possible hat length so that the transposition block is:
12345678
declivou
sabfghjk
mnpqrtwx
yz
The encrypting alphabet has 'a' being encrypted by 'G'. Locating 'a' in column 2 of the transposition block, and 'g' in column 5, we see the letter following 'a' is 'n', and the letter following 'g' is 'r'. Checking the encrypting alphabet we see that 'n' is indeed encrypted as 'R', so this key and hat length passes one of the type (1) consistency checks. Again, the encrypting alphabet has 'w' being encrypted as 'D'. Locating 'w' at the bottom of column 7, and 'd' at the top of column 1, we see that the letter following 'd' is 's', and 'S' is the encryption of 'c' which is in the top row of the transposition block, and is not in the column containing 'w', so this key and hat length passes a type (3) consistency check.
In fact this key and hat length passes a total of 7 consistency checks. Running our program on a list of 750,000 possible key words and phrases, the word DECLIVOUS was the only one that passed every consistency check. (The program took about 3 seconds to test the entire list.) And in fact it is the correct key for the headline puzzle.
Listing the DECLIVOUS key columns left to right we have:
dsmy eanz cbp lfq igr vht ojw ukx
Combining the key columns with the encrypting alphabet, there was only one order for joining the columns together into a slidable alphabet:
vhtdsmyukxlfqeanzojwcbpigr
LFQEANZOJWCBPIGRVHTDSMYUKX
Once you have a slidable alphabet solving the rest of the puzzle is easy. You can solve the rest of the headlines by looking at all shifts of the slidable alphabet against itself, and picking out the shifts that make the headlines comprehensible. Those shifts give you the setting for the headline puzzle. Combining the setting with the key gives you the numerical pattern for the hat. Searching word and phrase lists for possible hats that have the correct pattern should complete the solution.
In this particular example there was only one key word that passed all consistency checks. This will not always be the case. You may have several possible keys that pass all their consistency checks. But the key columns will have an order in which they can be joined together to get a slidable alphabet only for the correct key.
Finding the correct order in which to join the key columns can be automated also. The fastest way that I've found is to use hill-climbing on the column order. To score a column order you calculate how many different shifts it takes to slide each letter in the encrypting alphabet into place above the letter that encrypts it. You want to minimize this score. When the score drops to 1, so just one shifts correctly aligns all the letters, you have found your slidable alphabet. This hill-climbing process usually takes just a second or two to produce the correct column order, if there is one. If the program runs for several seconds without getting down to one shift, then the key you are testing is probably not the correct one.
Now you might want to try your hand at solving this Headline Challenge.
Headline Demo is a javascript program that uses this algorithm. (Requires Chrome or Firefox web browser).