JWS’s Puzzle and Cipher Programs

This is the pentomino puzzle. It is often sold as a plastic puzzle. The 12 pieces are all the possible forms that can be made out of five squares (hence the name ‘pentomino’, by analogy from ‘domino’ which is a shape made of two squares). The object of the puzzle is to fit all the pentominos into a box of size 10 x 6 squares. This is surprisingly difficult, but there are nevertheless thousands of ways to fit the pieces into the box (2339 of them, to be exact, not counting reflections and rotations of the whole box).

In 1988 I made a program that finds all solutions by recursive trial & error and displays them on the screen using text-mode ‘box draw’ characters. Not a very good program, but here it is: pento.zip (.EXE program for ms-dos, with C source code for ms-dos and Unix/Linux). Later I made better (faster) versions, for instance pento3.c (only for Linux/gcc).

However, later I found on Usenet a program by Tenie Remmel, which is clearly much better (penta.zip ). Not only does it run very fast, it has much better structure, so (with permission of the author) I used it as a basis for the experimental programs which follow.

More information on pentomino puzzles can be found here.

Puzzle pieces can also be made from other regular polygons; one well-known type is made from 6 equilateral triangles. Pieces made of 6 triangles are called hexiamonds (by analogy, of course, from ‘diamond’).  There are 12 different hexiamonds, not counting reflections and rotations. Plastic puzzles are sold in which you have to assemble the hexiamonds into various shapes; the simplest is the 6 x 6 diamond shown above.

With some modifications, Remmel’s program can be made to generate hexiamond solutions (printing them out by means of  ‘ASCII art’). The diamond shape (above) has only 156 solutions (excluding symmetries of the whole ‘box’), because many pieces do not fit well into the sharp corners.

shape A	shape B

The hexiamonds can also be assembled into other shapes; the puzzle is often sold in one of the shapes shown above. Changing a few lines of code in the program will generate the solutions. These shapes have lots more solutions than the diamond shape: 4968 for the one on the left, 5885 for the one on the right.

Download the program:  tri6.zip (C source code and ms-dos executable). Calling tri6 solves the diamond shape, tri6 -a  solves ‘shape A’, tri6 -b  solves ‘shape B’. Use redirection to store the solutions in a file, e.g. tri6 > myfile.txt .

Finally, puzzle pieces can also be made from regular hexagons. There are twenty-two different pentahexagons, puzzle pieces made from five hexagons. The figure above shows them arranged in a 22 x 5 parallelogram. It is natural to ask in how many ways this can be done.

Well, I don’t know (yet), but I think the number is huge. For instance, we can put in a restriction: let’s count only the number of ways the 22 pentahexagons can be arranged into two separate 11 x 5 parallelograms, like this:

This program (also based on Tenie’s pentomino code) will churn out (almost forever, and not very quickly: have patience before the first solution appears) solutions of the 5 x 22 puzzle: hex5.zip  (C source code + compiled version for ms-dos). The program can be modified easily to generate solutions of sub-arrays like the ones above, or of the 11 x 10 array.

This is the 3-ring puzzle. This can also sometimes be found as a plastic puzzle. It is a sort of 2-dimensional version of Rubik’s cube. By turning the rings you must try to make them of one color. The program 3RING.EXE (for ms-dos) is a computer version of this game (for EGA/VGA).

Download 3ring.zip (program with C source code for ms-dos) 

Gravestone at Pacitan (Indonesia)	The Vigenère cipher system is a famous classic cipher. To the left is an example of an inscription in Vigenère. A friend asked for my help in translating this. Of course we hoped to find a hidden treasure as in Edgar Allan Poe’s The Gold Bug. As it happened, there was no treasure (a sad family history was revealed), but this was why I started to make cryptology programs in the first place. The program vigenere.zip (.exe for ms-dos with C source code for ms-dos and Unix/Linux) decrypts Vigenère ciphers automatically. It works fine on Stage 4 of the Singh Cipher Challenge. The package also includes the ciphertext of, and some extra information about, the tombstone inscription pictured at the left. More information about the tombstone inscription is here and here.
Julius Caesar (died Ides of March, 44 B.C.)	The simplest kind of cipher is monoalphabetic substitution, sometimes called ‘the aristocrat of puzzles’. A very early example of monoalphabetic substitution was the cipher employed by Julius Caesar, which involved shifting the letters of the alphabet by 3 places (A->D, B->E, ..., Z->C). The following package helps you solve monoalphabetics (not limited to Caesar substitutions).  Download mono.zip (.exe for ms-dos with C source code for ms-dos) NOTE: NEW version, 16 January 2000, capable of handling long cryptograms (useful for stage 1 of the Singh Cipher Challenge..) NOTE: here is mono-nc.c, source code (to be compiled with ncurses) of the program for Linux.
a Playfair keysquare	A very nice 19th century cipher is the Playfair Cipher. In Playfair, letters are enciphered two at a time, using a key arranged in a 5 x 5 checkerboard. This program helps you to cryptanalyse Playfair cryptograms by reconstructing the keysquare. The program does the bookkeeping (and very well too), but you’ll have to provide the brainwork. Download playfair.zip (playfair.exe for ms-dos with playfair.c source code for ms-dos; comprehensive instructions and sample ciphertexts; will run in a ‘dos prompt’ or ‘command prompt’ on Windows, and of course also in dosemu on Linux). Note: NEW!! Latest improved version, 26 July 2006, with several enhancements (e.g. an undo function). Here is the same Playfair decoder for ‘native’ Linux: playfair-linux.tgz. Download in your home directory, do tar xfvz playfair-linux.tgz, move to the playfair-linux directory and read the instructions. This version has all the enhancements of the 2006 DOS/Windows version. It runs in terminal windows of (almost) arbitrary size (the ms-dos version is limited to an 80x25 terminal). It is in fact possible to write programs that solve Playfair ciphers entirely automatically by more or less random ‘trial and error’ methods. I made a program that can crack Stage 6 of the Singh Cipher Challenge in less than 3 seconds; faster programs are no doubt possible. But of course, there isn’t much fun in a completely automated solution.
Enigma machine	The most famous 20th century cipher was the one produced by the German Enigma cipher machine. The British set up a huge organisation to crack these ciphers using electro-mechanical machines and early electronic computers. They would have had an easier time if they’d had some modern PC’s. The following program cracks Enigma ciphertexts of sufficient length automatically in about a minute. I made it for solving Stage 8 of the Singh Cipher Challenge (which has now ended, and the solutions of which have been published, so making this program available no longer spoils the contest). The program implements a highly efficient method invented by Jim Gillogly. Download enigma.zip (exe for ms-dos and C source code for ms-dos and Unix/Linux -- slightly improved 2005 version).