c# - Programming Contest Question: Counting Polyominos

Question

Please see my own answer, I think I did it!

---

Hi,

An example question for a programming contest was to write a program that finds out how much polyominos are possible with a given number of stones.

So for two stones (n = 2) there is only one polyominos:

XX

You might think this is a second solution:

X
X

But it isn't. The polyominos are not unique if you can rotate them.

So, for 4 stones (n = 4), there are 7 solutions:

X
X   XX   X    X     X   X
X   X    XX   X    XX   XX   XX
X   X    X    XX   X     X   XX

The application has to be able to find the solution for 1 <= n <=10

PS: Using the list of polyominos on Wikipedia isn't allowed ;)

EDIT: Of course the question is: How to do this in Java, C/C++, C#

---

I started this project in Java. But then I had to admit I didn't know how to build polyominos using an efficient algorithm.

This is what I had so far:

import java.util.ArrayList;
import java.util.List;


public class Main
{

    private int countPolyminos(int n)
    {
        hashes.clear();
        count = 0;
        boolean[][] matrix = new boolean[n][n];
        createPolyominos(matrix, n);
        return count;
    }

    private List<Integer> hashes = new ArrayList<Integer>();
    private int count;

    private void createPolyominos(boolean[][] matrix, int n)
    {
        if (n == 0)
        {
            boolean[][] cropped = cropMatrix(matrix); 
            int hash = hashMatrixOrientationIndependent(matrix);
            if (!hashes.contains(hash))
            {
                count++;
                hashes.add(hash);
            }
            return;
        }
    // Here is the real trouble!!
    // Then here something like; createPolyominos(matrix, n-1);
    // But, we need to keep in mind that the polyominos can have ramifications
    }

    public boolean[][] copy(boolean[][] matrix)
    {
        boolean[][] b = new boolean[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; ++i)
        {
            System.arraycopy(matrix[i], 0, b, 0, matrix[i].length);
        }
        return b;
    }

    public boolean[][] cropMatrix(boolean[][] matrix)
    {
        int l = 0, t = 0, r = 0, b = 0;
        // Left
        left: for (int x = 0; x < matrix.length; ++x)
        {
            for (int y = 0; y < matrix[x].length; ++y)
            {
                if (matrix[x][y])
                {
                    break left;
                }
            }
            l++;
        }
        // Right
        right: for (int x = matrix.length - 1; x >= 0; --x)
        {
            for (int y = 0; y < matrix[x].length; ++y)
            {
                if (matrix[x][y])
                {
                    break right;
                }
            }
            r++;
        }
        // Top
        top: for (int y = 0; y < matrix[0].length; ++y)
        {
            for (int x = 0; x < matrix.length; ++x)
            {
                if (matrix[x][y])
                {
                    break top;
                }
            }
            t++;
        }
        // Bottom
        bottom: for (int y = matrix[0].length; y >= 0; --y)
        {
            for (int x = 0; x < matrix.length; ++x)
            {
                if (matrix[x][y])
                {
                    break bottom;
                }
            }
            b++;
        }

        // Perform the real crop
        boolean[][] cropped = new boolean[matrix.length - l - r][matrix[0].length - t - b];
        for (int x = l; x < matrix.length - r; ++x)
        {
            System.arraycopy(matrix[x - l], t, cropped, 0, matrix[x].length - t - b);
        }
        return cropped;
    }

    public int hashMatrix(boolean[][] matrix)
    {
        int hash = 0;
        for (int x = 0; x < matrix.length; ++x)
        {
            for (int y = 0; y < matrix[x].length; ++y)
            {
                hash += matrix[x][y] ? (((x + 7) << 4) * ((y + 3) << 6) * 31) : ((((x+5) << 9) * (((y + x) + 18) << 7) * 53));
            }
        }
        return hash;
    }

    public int hashMatrixOrientationIndependent(boolean[][] matrix)
    {
        int hash = 0;
        hash += hashMatrix(matrix);
        for (int i = 0; i < 3; ++i)
        {
            matrix = rotateMatrixLeft(matrix);
            hash += hashMatrix(matrix);
        }
        return hash;
    }

    public boolean[][] rotateMatrixRight(boolean[][] matrix)
    {
        /* W and H are already swapped */
        int w = matrix.length;
        int h = matrix[0].length;
        boolean[][] ret = new boolean[h][w];
        for (int i = 0; i < h; ++i)
        {
            for (int j = 0; j < w; ++j)
            {
                ret[i][j] = matrix[w - j - 1][i];
            }
        }
        return ret;
    }

    public boolean[][] rotateMatrixLeft(boolean[][] matrix)
    {
        /* W and H are already swapped */
        int w = matrix.length;
        int h = matrix[0].length;
        boolean[][] ret = new boolean[h][w];
        for (int i = 0; i < h; ++i)
        {
            for (int j = 0; j < w; ++j)
            {
                ret[i][j] = matrix[j][h - i - 1];
            }
        }
        return ret;
    }

}

Answer 1

There are only 4,461 polynominoes of size 10, so we can just enumerate them all.

Start with a single stone. To expand it by one stone, try add the new stone in at all empty cells that neighbour an existing stone. Do this recursively until reaching the desired size.

To avoid duplicates, keep a hash table of all polynominoes of each size we've already enumerated. When we put together a new polynomino, we check that its not already in the hash table. We also need to check its 3 rotations (and possibly its mirror image). While duplicate checking at the final size is the only strictly necessary check, checking at each step prunes recursive branches that will yield a new polynomino.

Here's some pseudo-code:

polynomino = array of n hashtables
function find_polynominoes(n, base):
  if base.size == n:
    return
  for stone in base:
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
      new_stone.x = stone.x + dx
      new_stone.y = stone.y + dy
      if new_stone not in base:
        new_polynomino = base + new_stone
        is_new = true
        for rotation in [0, 90, 180, 270]:
          if new_polynomino.rotate(rotation) in polynomino[new_polynomino.size]:
            is_new = false
            break
        if is_new:
          polynomino[new_polynomino.size].add(new_polynomino)