pentomino
(Translation of article "Programmeren van de pentomino puzzle" from 047_1971-72_03.pdf)
We intend to use a computer program to find all solutions to the 6 x 10 pentomino. This is a jigsaw puzzle in which you are asked to fill a rectangle 6 units high and 10 units wide (the 'board') with 12 given 'pieces', shown in Fig. 1. Each of these pieces can be thought of as being constructed from 5 unit squares by sticking them together along entire sides. In fact, there are exactly 12 different pieces that can be obtained this way. Two pieces are called equal when they are congruent; mirrored figures are also called congruent. The latter is related to the fact that the pieces can be flipped over: they have no clear front or back.
One easily senses, and with some effort can prove, that in a solution a piece can only be placed on the board in such a way that the unit squares of the piece coincide with five of the 60 unit squares into which one can think of the board divided. If one dispenses with translations, the pieces, except for the first one (the cross), can still be placed on the board in different ways. In this way 63 figures are created that we will call 'slices', drawn in figure 2. The pieces drawn in figure 1 give rise to respectively 1, 4, 4, 4, 4, 4, 2, 8, 8, 8, 8, 8 slices.
To each solution one can add a series of 12 slices so that different slices yield different series. This can be done in many ways; we will stick to the following way, which we will describe with the help of fig. 3 and fig. 4. In the solution of fig. 3 we will go through the 60 squares, starting with the first column from top to bottom, then the second column from top to bottom, etc. Each time we come to a new slice for the first time, we place a mark, and we note the slices in the order in which we found them. This is done in fig. 4. We will call such a series of slices a word, the slices are called letters, and the collection of 63 slices is called the alphabet.
It is clear that for each slice the mark ends up in the leftmost column of the slice, and in that column on the highest square. The position of the mark on the slice does not depend on the solution; we can indicate the marks on the slices a priori. This has been done in fig. 2. Conversely, the solution from fig. 3 can be found from the word in fig. 4. The first slice is placed with its mark on the square at the top left. The squares are traversed and the first unoccupied field ('first hole') is sought; the second slice is placed there with its mark. The squares are traversed further to what is now the first hole, and the third slice is placed there, etc. By 'traversing' we naturally mean scanning column after column, each from top to bottom.
Not every series of 12 'letters' is a usable word. If we apply the procedure outlined in the previous paragraph to the word in fig. 5, it fails at the fourth slice because of overlap. We also see in another way that the word does not correspond to a solution: the cross appears twice! However, we will not look for errors at the end of a word, and will always read the word from the beginning, and declare letter by letter acceptable until we eventually come across an unacceptable letter. Unacceptable can mean (i) it overlaps slices that have already been laid, (ii) it protrudes over the edge, (ii) the piece is no longer available because we already have it on the board in one position or another.
Because we scan words from left to right, we can draw a parallel with the pronounceability of a word with certain pronunciation rules. Here too, we can judge words by working from the left (at least when the language is such that the beginning of a pronounceable word is also pronounceable). A word of 12 or fewer letters, with the 63-letter alphabet of Lig. 2, we will call pronounceable if the slices of that word can be placed on the board in succession, according to the rule of marking on the first hole, and without any slice being unacceptable because of one of the above-mentioned rules (i), (ii), (iii).
We now consider an alphabetically ordered list of all words of 12 or fewer letters. The order in the alphabet is that of fig. 2. We are looking for all pronounceable words in it, and in particular those of 12 letters. The latter are the solutions to our problem.
It is impossible to have the entire word list tested for pronounceability by a computer. That list contains 63 + 63^2 + . . . + 63^12 words, and that would take a fast modern computer with the smartest program another hundred million years. The objection that we will have much faster devices for a large part of that period is a poor consolation for us at the moment. What is very possible, however, is to have a computer go through all pronounceable words and print out all 12-letter words from that list. That need not take a fast computer with suitable programming much more than half an hour these days. To enable the computer to find the pronounceable words, we let it run through the test words. A test word is a word of < 12 letters that becomes pronounceable by omitting the last letter. The pronounceable words are therefore also test words. The empty word is considered pronounceable, so that all words of one letter are test words. Very roughly, we now have the following program:
- Start with the first test word.
- If the test word under consideration is a pronounceable word of 12 letters, write that down as the solution.
- Check whether there is a next test word. If there is none, the test word list is finished; if there is one, go to 2.
We now look at what needs to be done in III. If our test word is pronounceable with fewer than 12 letters, the next test word is obtained by adding the first letter of the alphabet. In all other cases, the next test word is found by 'raising' the last letter, i.e. replacing it with the next letter of the alphabet. In the case that the last letter of the test word is also the last letter of the alphabet, we remove the last letter and replace the last letter of the new word with the next letter of the alphabet. If it was already the last letter of the alphabet, we break it down further, etc. See figure 6.
If our test word is pronounceable, but has exactly 12 letters, there is no chance of pronounceability by changing the last letter, because the gap created by removing the last slice has an area of 5, and no other slice fits in there. This means that we can skip something; In the block diagram of Fig. 6 we can, if desired, walk directly from the no output of '<12 letters? ' to point γ instead of to point β.
We now want to indicate how the question 'pronounceable' from the block diagram of fig. 6 is treated. Since the question is only asked for test words, it is already known that it only concerns the last letter, because after omitting that letter the word is pronounceable. A set of slices placed on the board corresponds to this pronounceable piece (cf. § 2). We will not have to build up this 'board situation' from that word, because the changes in that word only concern the last letter (addition, omission or modification). We will therefore always remember the board situation and update it when appropriate. Furthermore, we will have to keep a list of the letters of the word. If k is the number of letters of the test word, then we have to note down the 1st letter, . . . , (k-1)th letter somewhere, as well as the (possibly unacceptable) k'th letter. The row of letters 1'th to (k-1)th is called the 'stack'. We call it a stack because the only operations we perform are: removing the top one and placing a new one on top. The first letter is at the bottom. The number k is called the floor; it is the height at which we intend to place the next letter.
If we want to know whether the test word of k letters is pronounceable, we start from the board situation of the first k—1 pieces known to us, and we see whether the th slice (with a mark on the first hole) can be added. The board situation indicates which of the 60 fields are occupied. The first hole can be determined from this. It is wise not to calculate that first hole again each time, but to derive it from the previous situation. With this in mind, it is useful to indicate on the stack not only the placed slices, but also the position of each slice that its mark occupies on the board. When we then remove slices at the end of the word, the new first hole can be read directly from the stack.
In addition to the stack, the floor, the number of the th letter (the slice number), and the board, we also have to keep track of the magazine. This consists of 12 memory locations on which it is noted which of the 12 pieces are still available. Pronounceability depends on nI. not only depends on the placeability of the ke slice, but also on the question of whether the piece in question was already on the board before.
We will now further elaborate the block diagram of fig. 6 to that of fig. 7. In corresponding places in the block diagrams of fig. 6 and fig. 7 letters a, 0, y have been added, so that it is clear how fig. 7 originated from fig. 6. (Note the remark made at the end of § 5).
We will now choose codes for the various items. First, we provide the sign with a bottom edge and a right edge, and we number the fields as indicated in figure 8. Fields 7, 14, 21.....70 and 71 to 77 are always considered occupied. This will prove to have the advantage that points (i) and (ii) from the end of § 2 are treated in exactly the same way. Furthermore, we indicate the four so-called relational positions for each slice. The position on the sign of each square of the slice can be calculated by adding a number that does not depend on the position of the slice to the position occupied by the mark. For example, the relative positions of slice 21 (see figure 9) are 6,7,12,13. When one tries to place this slice with a marker on board square 2, one calculates by adding that space is now requested on 8,9,14,15. That space is not there, because as said, square 14 is permanently occupied. One sees how squares 7, 14......70 provide both the protection against exceeding the lower edge and the upper edge. The left edge of the board does not need to be protected, because the relative positions are always positive.
The relative positions will be stored in four rows of length 63 each. They are called relposeen, relposttwee, relposdrie, relposvier. For example, relposdrie (21) = 12; it is the third relative position of slice 21. (To prevent board positions > 77 from ever being consulted, we agree that for each slice the relative positions are in ascending order).
In order to be able to keep the warehouse administration, we have set up the row 'piece no.'. For example, piece no. (12) = 4 because the 12th slice is a position of the 4th slice.
The rows mentioned are filled by means of a number tape that contains all this data. On this tape are successively the relative positions and piece no. of the first slice (6,7,8,14,1), the corresponding ones for the second slice (1,7,14,15,2), etc.
The warehouse is a row of 12 numbers; warehouse(i) = 1 means that the i-th piece is in the warehouse, warehouse(i) = 0 means that the i-th piece is on the board.
We now discuss the program written in ECOL3. For the sake of discussion, we have given each ECOL line a number as a label, and not only to the lines that are actually referred to in the program.
In lines 1 to 10, the various rows are declared. We also point out 'sticky stack' in which the numbers of the slices placed on the board are kept, and 'hole stack' for the positions of the markings of those slices. (We call this 'hole stack' because at the moment of placing the slice, the marking ends up on what is at that moment the first hole.)
In lines 11 to 18, the reading of the number tape is provided.
In lines 19 to 25, fields 3,9,10,16,17,23,24 mentioned in § 10 are placed in a row 'crossing place'. Line 26 initializes the solution number that will be printed with each solution.
Lines 27,28, together with 116 and 117, regulate the successive cross positions: In lines 41 to 49 the cross is placed on the board (because the numbers 6,7,8,14 are set in the program, reading in these four numbers was actually unnecessary). Before this cross is filled in, however, the board is first cleaned (lines 29 to 32) and the edge is filled (lines 33 to 40).
In lines 50 to 54 the magazine is filled.
With lines 55 to 58 field 1 is made the first hole. (From line 84 you can jump back to line 56). In general, lines 56,57,58 ensure that after placing a new piece on the board, the search continues for the next field that is still free. Rule 59 indicates the first slice; because slice 1 is no longer in play, 2 is the first slice number.
At rule 60 we have the place indicated in the block diagram with a; likewise, rules 94 and 96 correspond to 0 and y respectively.
Lines 60, 61, 62 ask whether the piece is in the magazine, and lines 63 to 74 check whether the slice fits; in case of failure we end up at 94. If it does succeed, the piece is taken from the magazine (line 75) and the slice is placed on the board (76 to 80). In 81 and 82, the slice with the then valid first hole is noted on the stack, and the floor is raised to be ready for the next slice. If the 12th floor is reached, there is a solution (i.e. 11 slices placed) that is printed (with the solution number mentioned). The latter is done in lines 85 to 93. If the answer to line 84 is affirmative, the new first hole must be determined and slice number 2 must be made. This is done by referring to line 56, which leads us back to line 60.
Lines 94 and 95 correspond to the two instructions from the block diagram (fig. 7) at point 0.
Line 96 corresponds to 'y. Instead of 'READY' we end up at 116 to set a new position of the cross. Line 98 reads off what the first hole is after the last slice has been removed: that was the position of the mark of the removed slice remembered on the 'hole stack'. In line 99 the number of the slice is read off, in order to be able to determine (via 115) the next slice at 94. Note that at 97 the floor has been lowered, but that no effort has been made to first leave the previous floor clean. After all, nothing is read off there before it has been written over again.
Lines 100 to 114 are the 'reversals' of 75 to 80. Here is the program:
(source code)