A planar polyomino of size n is an edge-connected set of n squares on a rectangular two-dimensional lattice. Similarly, a d-dimensional polycube (for d > 2) of size n is a connected set of n hypercubes on an orthogonal d-dimensional lattice, where two hypercubes are neighbors if they share a (d — 1)-dimensional face. There are also two-dimensional polyominoes that lie on a triangular or hexagonal lattice. In this paper we describe a generalization of Redelmeier's algorithm for counting two-dimensional rectangular polyominoes, which counts all the above types of polyominoes. For example, our program computed the number of distinct three-dimensional polycubes of size 18. To the best of our knowledge, this is the first tabulation of this value.
展开▼
