enumerating polyominos

Question

Polyominoes are made by gluing together finitely many squares along their edges. They always have connected interiors, but are allowed to have holes.

Enumerating polyominoes is a huge subject, and of course the answers depend on whether you are interested in free, one-sided, or fixed polyominoes. I am trying to understand one of the most fundamental algorithms in this area, although I'm aware that faster, but more complicated, algorithms are known now.

Specifically, I'm interested in Redelmeier's algorithm for enumerating fixed polyominoes:

https://en.wikipedia.org/wiki/Polyomino#Algorithms_for_enumeration_of_fixed_polyominoes

You can find the original paper here: https://dx.doi.org/10.1016%2F0012-365X%2881%2990237-5

And in case that link is behind a paywall, the algorithm is described in Section 2 here: https://arxiv.org/pdf/1106.1078.pdf

I am having trouble understanding the recursive description of the algorithm in the original paper, and I find the Wikipedia description much easier to understand. Unfortunately, I am not sure if what is on Wikipedia is correct. What is bothering me is that the algorithm described can get stuck sometimes, where no further tiles can be added to the current polyomino. (In fact, if you try to generate a "random" polyomino with 1000 tiles, you will almost always get stuck at some point.)

The smallest example I have is illustrated below. This seems to follow the rules described on Wikipedia, but now we are stuck.

Answer 1

I am also struggling to understand the details and must also conclude that the paper is just not written very well. It doesn't properly distinguish global state from local, for example.

Wikipedia makes a nice try with the numbers, but the devil is in the details, which aren't mentioned. Once I get my head around it, I may improve the Wikipedia page with pictures. For now though, I think I can answer this question.

This "getting stuck" also happens with the original algorithm. It's not a problem: your recursive calls simply return without generating any new polyominos, until a call higher up the stack can continue somewhere else. Note that Redelmeier's paper mentions in the text above the pseudocode:

The following steps are repeated until the untried set is exhausted.

In some cases, a recursive invocation would receive an empty untried set right off the bat, and so it would return without doing anything at all. Then the parent call would continue with another neighbour.

Answer 2

This is an old question and probably not relevant anymore, but since I like this algorithm I'll give it a shot.

The basic idea in Redelmeier is to carefully manage the set of squares that can be added to the polyomino - the so-called "untried set". The algorithm is basically this:

Start with the empty polyomino and the untried set containing only the origin, [(0,0)]

Perform the following recursively:

1. While the untried set is not empty, remove a square from it and add to the current polyomino
2. Count this polyomino - this is the only time it will be generated in the algorithm (one can also print it to a file etc. at this stage).
3. Create a copy of the untried set. This is very important that we work with a copy (since this copy is going to be emptied in the subsequent recursive call).
4. To this copy add all of the new neighbors of the current polyomino, and then recursively return to 1, with the new polyomino and untried set, unless the current polyomino is already of the requested maximal size.
5. After returning from the recursion, remove the new square you've added to the polyomino at stage 1, and proceed to the next element of the untried set.

The most important part here is how new neighbors are defined. This are cells that are:

1. Neighbors of the new square we just added to the polyomino at this stage.
2. Are not part of the current polyomino and are not neighbors of the current polyomino (before we added the new square)
3. Are not out of the grid (in order to avoid double-counting, the grid only contains the cells (x,y) where $y>0$ or $y=0$ and $x\ge0$).

The algorithm can indeed get "stuck" in the sense that a specific branch of the recursion cannot add more squares to the current polyomnino, but it's not a problem; any polyomino will be counted at some branch. Which branch depends on the order in which elements are sorted in the untried set.

In your example we only see the current polyomino, not the untried set, so it's hard to understand in which sense we are "stuck". For example, cell 19: it won't be added to the untried set when adding 42 since it's not a new neighbor, but it should already be in the untried set (it was added when 16 was added). If it's not in the untried set in this stage, it means that earlier, in another branch of the recursion, all the polyominoes containing 19 were already counted; now we are counting all the polyominoes not containing 19, so not adding 19 again doesn't mean we lost anything.

I hope this helps future readers arriving here. I'm also attaching an ad-hoc Python code for computing this; it's sometimes easier to understand from a working code.

import copy
def neighbors(polyomino):
    found = []
    for (x,y) in polyomino:
        for delta_x, delta_y in [(1,0), (-1,0), (0,1), (0,-1)]:
            if y + delta_y < 0 or (y + delta_y == 0 and x + delta_x < 0):
                continue
            new_square = (x + delta_x, y + delta_y)
            if new_square not in found:
                found.append(new_square)
    return found

def redelmeier(n):
    counts = [0] * (n+1)
    counts[0] = 1
    polyomino = []
    untried_set = [(0,0)]
    redelmeier_recursion(n, counts, polyomino, untried_set)
    return counts

def redelmeier_recursion(n, counts, polyomino, untried_set):
    while len(untried_set) > 0:
        new_square = untried_set.pop()
        new_untried_set = copy.copy(untried_set)
        new_square_neighbors = neighbors([new_square])
        polyomino_neighbors = neighbors(polyomino)
        for s in new_square_neighbors:
            if s not in polyomino_neighbors and s not in polyomino:
                new_untried_set.append(s)
        new_polyomino = copy.copy(polyomino)
        new_polyomino.append(new_square)
        counts[len(new_polyomino)] += 1
        if len(new_polyomino) < n:
            redelmeier_recursion(n, counts, new_polyomino, new_untried_set)