If you are not familiar with the Tridigital cipher, go to the American Cryptogram Association cipher types page and be sure you understand how it works. I’ll use the same keyblock on that page as an example.

N O V E L C R A F T
6 7 0 3 5 2 8 1 4 9
D R A G O N F L Y -
B C E H I J K M P -
Q S T U V W X Z - -

pt: t h e   i d e s   o f   m a r c h
CT: 0 3 0 9 5 6 0 7 9 5 8 9 1 0 7 7 3.

Note that every plaintext letter has only one digit that represents it, i.e. plaintext D is always enciphered with 6 in this case. The opposite is not true. The 6 can also represent B or Q. The spaces in the plaintext are always represented by the digit on the far right, 9 in this case. In the example, 0 is the highest digit and represents 10. The columns are numbered in alphabetical order according to the “hat” NOVELCRAFT. The ciphertext is a string of digits.

Step 1 is to find the spaces in the ciphertext, that is, determine which digit is the one on the far right. Since the plaintext will never have two spaces in a row, most digits can be eliminated by the fact they appear doubled in the ciphertext. For others, it is usually easy to judge by using the lengths of the words that would be produced by the possibilities. One might result in a 27-letter word, another in five different one-letter words. Those you can eliminate. This is just a preliminary step, not the heart of the algorithm.

Step 2. Once you have the ciphertext divided into word lengths with spaces inserted you need to prepare your word lists. Create arrays for each word length. To speed up solution I order the words by frequency, i.e. how common they are in English, but this is not necessary.

Step 3. Create an array of the ciphertext words, ordering them from longest to shortest, but keep a key so you can restore them to the order they appear in the original text. In the example, the elements would be 10773, 5607, 030, 58. In real problems, there are going to be some longer words, which is essential to an efficient algorithm.

Step 4. Begin testing words of the right length for the first word. Check for conflicts. Since WHICH is the most common 5-letter word, that would be the first one tested. We see the H’s would be represented by two different digits, 0 and 3, so it cannot be the first word. Go to the next word, THEIR in my list. There are no conflicts. The E and I may both be in the same column in the keyblock and thus both represented by 7. Save the word in a temporary array or string of possible solutions. Feed this word into recursive routine that is the key to the algorithm along with the level, i.e. 1 ion this case since this is the first word.

Step 5. Recursion. The recursive routine must first check to see if it has already completed all the levels. If it has, it has found a possible solution. That should be printed, displayed or saved in some fashion unless its score makes it untenable (I’ll discuss scoring later). If it’s not yet complete, start testing words from the next word list, the one with words the same length as the next level. In our example, that’s words of length 4 for word two, ciphertext 5607. In my list, THAT would be the first word tested and it would conflict with its own ciphertext (T would be represented by 5 and 7) as well as with the first word.  In my list, the first 16 words would conflict, landing on SOME as a possibility. The E is represented by 7 in both words, THEIRSOME. This combination is fed back into the recursion routine with the new level (2, here) and the process is repeated until a full solution is found or all the words on some level are tried without finding a possibility to send on to the next level. The trial words are then backed out of the temporary array or string and the next word at each level is tried until all the levels are tried back to level one where the process is repeated.

The experienced programmer, or cryptographer, will realize that the process as described above will eventually find the solution, but would take impractically long, especially with longer ciphertexts. The key to making this work is to find an efficient way to prune the words tried. There are two basic ways I’ve found, although there may be others. The two I use are key testing and scoring. I’ll save those for my next post.