Programming Contest Question: Counting Polyominos

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)

The most naive solution is to start with a single X, and for each iteration, build the list of unique possible next-states. From that list, build the list of unique states by adding another X. Continue this until the iteration you desire.

I'm not sure if this runs in reasonable time for N=10, however. It might, depending on your requirements.

Just solved this as well in java. Since all here appear to have performance issues. I give you mine as well.

Board reprsentation:

2 arrays of integers. 1 for the rows and 1 for the columns.

• Rotation: column[i]=row[size-(i+1)], row[i] = reverse(column[i]) where reverse is the bits reversed according to the size (for size = 4 and first 2 bits are taken: rev(1100) = 0011)
• Shifting block: row[i-1] = row[i], col[i]<<=1
• Check if bit is set: (row[r] & (1<<c)) > 0
• Board uniqueness: The board is unique when the array row is unique.
• Board hash: Hashcode of the array row
• ..

So this makes all operations fast. Many of them would have been O(size²) in the 2D array representation instead of now O(size).

Algorithm:

• Start with the block of size 1
• For each size start from the blocks with 1 stone less.
• If it's possible to add the stone. Check if it was already added to the set.
• If it's not yet added. Add it to the solution of this size.
  • add the block to the set and all its rotations. (3 rotations, 4 in total)
  • Important, after each rotation shift the block as left/top as possible.
• +Special cases: do the same logic for the next 2 cases
  • shift block one to the right and add stone in first column
  • shift block one to the bottom and add stone in first row

Performance:

• N=5 , time: 3ms
• N=10, time: 58ms
• N=11, time: 166ms
• N=12, time: 538ms
• N=13, time: 2893ms
• N=14, time:17266ms
• N=15, NA (out of heapspace)

Code: https://github.com/Samjayyy/logicpuzzles/tree/master/polyominos