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.

pentomino

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.

 

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 .

 

trictri6b

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:

 

We may reasonably think that each of these two sets of 11 pentahexagons may be arranged in a large number of ways. Actually, the left side can be rearranged in 614 ways, the right side in 36 ways; this gives a total number of arrangements of 11052 (614 x 36 / 2; division by 2 to exclude symmetries of the whole array).  So that’s only for this division of the set of 22 into two sets of 11. The number of such divisions is 22!/(11! x 11!), a huge number. Not all of them are possible solutions, but quite a lot of them are (which ones? An interesting question by itself). So that gives us an idea of the number of restricted solutions. The mind boggles when thinking of the size of the whole solution set! Despite this enormous number of solutions, finding even one by hand is very difficult.

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).

Comments
Simplue WordPress theme, Copyright © 2013 DicasLivres.org Simplue WordPress theme is licensed under the GPL.