Application Series 21

IT MIGHT BE A QUESTION OF POLYOMINOES

SIR user Dave Doulton, who is Senior Computing Officer specialising in databases at University of Southampton, has posed a squarish problem and used SIR to find the answer.

The Problem

Dave explains the intricacies of polyominoes and why they are of interest to mathematicians. 'A polyomino is a generalisation of the domino which, as we all are aware, is a shape consisting of two squares joined along one edge. The degenerate form of the polyomino is the square (monomino). The form with three squares is a tromino and with 4 squares the tetromino (the basis for the popular computer game of tetris)'.

But the thing that interests Dave is how many shapes polyominoes can take. 'The first two, square and domino, have only one possible shape, however once past this level the number of possible shapes begins to increase, quite rapidly' Dave said 'The hope is to be able to predict exactly how many shapes there will be for an n-omino'.

The Program

Dave's original program to count the shapes for an n-omino was a very simplistic BASIC program written for a Hewlett Packard 2000F in 1975. The basic method used was to add an extra square to each side of each square for each of the (n-1)-omino shapes. 'The coordinates of this square's centres were stored in an array. The shapes were rotated, and reflected into all possible orientations and compared with ones already stored to discard matching shapes.' Dave pointed out. Once the number of squares becomes larger, the number of comparisons begins to slow things down tremendously. 'The first version of the program, producing numbers of shapes for up to 6 squares, took 24 hours' Dave claimed.

Developments

Several improvements have been made to the algorithm, by reducing the number of checks and improving the search speed. However this has lead to an additional complexity, as the algorithm now needs an upper estimate of the number of shapes expected.

If the original shape is symmetric then it is only necessary to test some of the positions as the others will be duplicates. Symmetry is checked by counting the number of times that a rotation or reflection fits on top of the given shape.

The coordinates of the centres of the squares were converted to letters of the alphabet in pairs. The first square would have coordinates (0,0) which would become AA a domino (0,0),(0,1) would become AAAB and so on. The string was then stored by hashing it into a large array. 'Now the whole array does not have to be searched only the entries around the point generated from the hash algorithm need checking' Dave explained. Collisions were coped with by keeping a note of the maximum distance moved in order to store a colliding element and then searches only moved that distance from the target location.

Each time a new coordinate string is stored it is also written to a file as a permanent record. This file can be read in order to generate the next size polyominoes. By late 1995, files exist for all polyominoes up to order 15. 'The job to create the 15s from the 14s started at 14:16:47 on the 9th May and finished at 04:08:00 on the 10th May using an 8 processor Sun Sparc 1000. Compare that to the original' Dave said proudly.

Unfortunately this is the largest job that can be run this fast on the machines Dave has available as it is necessary to hold the array in memory to achieve this sort of speed and the next size would need more than the maximum real memory.

What about SIR?

At this point the thought of using SIR/HOST to store the data whilst keeping the rest of the program the same arose. SIR/HOST is the 3GL interface to SIR's database structure which enables users to adapt the code they have already written to SIR's relational database structure. 'This way the data for each size would be stored in one place and the program would not have to cope with the hashing' Dave explained. There was minimal extra coding needed to cope with the database and the program works well.

Once a version was running with HOST the next thought was of trying SIR's 4GL language, PQL, to compare with the HOST version. Using subroutines the program generally converted with ease to PQL. Development time was significantly shorter in PQL although run time was longer with the 4GL, as expected.

The Results

So after all this, is Dave any closer to answering his original questions? The number of polyomino shapes for up to 15 squares is tabulated below.

To solve the question of predicting the number of n-omino shapes, Dave graphed the ratio of numbers of n-omino shapes to those of (n-1)-omino shapes:

This ratio seems to be approaching 3.8. This can therefore be used as an approximation to the number of polyomino shapes of the next size.

For more information on the use of SIR with mathematics contact:
Dave Doulton
Computing Services
University of Southampton
Highfield Southampton SO9 5NH UK

Back Sir Home