What is the most efficient way to generate all possible shapes formed by 10 orthogonally connected points?

Question

I need to generate all valid combinations of 10 points in a 2D space.

In this case, a valid shape means:

1. All points are attached to each other and diagonal connection is not allowed.
2. if we draw an outside boundary around points, there should be no empty points inside the shape.

Here are some examples of valid and invalid combinations:

I tried several algorithms but they were all inefficient and take too much time to calculate. What would be the most efficient way to generate and store all valid combinations?

I need it for generative design purposes. A combination represents a shape of a room in an architectural floorplan. Preferable language is Python.

Answer 1

The code below prints all possible structures that can be made by connecting n points orthogonally. It is pretty efficient for your use case, for n=10 it runs in about 4 seconds in my laptop with the validity check (no gap in the room). Based on the running time for n=8, 9, 10, 11, it seems that the time complexity is O(4^n), which makes sense, given the four cardinal directions.

The idea is to first place one point, then repeatedly consider the places where we can place the points such that any constraint is still satisfied. At each step, we consider the outer boundary of any points in the structure that have not been part of any consideration before, and consider all possible combinations of filling these spaces with any number of points that we have left.

The constraint of no gap within the room is validated by depth-first search from empty cells that are next to points that have just been selected. If at any point during the DFS it reaches the wall or has walked far enough, then it is valid.

Here is the code (requires Python 3.6+ for yield from and f-string):

# -*- coding: utf-8 -*-
"""
02 Aug 2019
Generate all possible floorplans.
https://stackoverflow.com/questions/57310325/
"""

# Import statements
from __future__ import print_function, division
import sys
from argparse import ArgumentParser
from pprint import pprint
from itertools import combinations

def neighbors(row, col):
    """Generate all neighbors of a point"""
    result = []
    for dir_row, dir_col in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
        new_row, new_col = row+dir_row, col+dir_col
        result.append((new_row, new_col))
    return result

def generate_structures(n):
    """Main generator to generate structures that can be formed from n orthogonally connected
    points."""
    # Setup the grid
    # The first point is assumed to be the left-most point, and among the left-most,
    # it is the top-most. This prevents duplicate structures, since all structures have a
    # unique left-most top-most point.
    grid = [['.']*n for _ in range(2*n-2)]
    for r in range(len(grid)):
        grid[r].append('X')
        grid[r].insert(0, 'X')
    grid.append(['X']*(n+2))
    grid.insert(0, ['X']*(n+2))
    row, col = n-1, 1
    for r in range(row):
        grid[r][1] = 'X'
    grid[row][col] = 'O'
    yield from _generate_structures(grid, n-1, [(row, col)], (row, col), n-1)

def _generate_structures(grid, n, last_points, source, max_dist):
    """Recursive function to generate all possible structures with n points remaining,
    where last_points are the points last added.

    The source and max_dist are used in validation check, to make it slightly faster.
    """
    if n == 0:
        # No more points to be placed, return the current structure
        yield grid
        raise StopIteration
    def get_expansion(points, charset='.'):
        """Get all points around selected points, with the given character set."""
        expansion = set()
        for row, col in points:
            if grid[row][col] != 'O':
                # Only expand from points
                continue
            for new_row, new_col in neighbors(row, col):
                if grid[new_row][new_col] not in charset:
                    continue
                expansion.add((new_row, new_col))
        expansion = list(sorted(expansion))
        return expansion
    expansion = get_expansion(last_points)
    # For all possible number of points that can be assigned to the boundary
    # of the last added points (1 to n)
    for i in range(1, n+1):
        # Consider all the possible combinations (number of empty space choose
        # number of points)
        for combination_indices in combinations(range(len(expansion)), i):
            includeds = [False]*len(expansion)
            included_points = []
            for included_index in combination_indices:
                includeds[included_index] = True
            for included, (row, col) in zip(includeds, expansion):
                if included:
                    grid[row][col] = 'O'
                    included_points.append((row, col))
                else:
                    grid[row][col] = 'X'
            to_be_checked = get_expansion(included_points, '.X')
            if valid(grid, to_be_checked, source, max_dist-n+1):
                # If valid (there are no isolated empty cells, for example),
                # then continue expanding the boundary.
                yield from _generate_structures(grid, n-len(included_points), included_points,
                                                source, max_dist)
            for row, col in expansion:
                grid[row][col] = '.'

def valid(grid, points, source, max_dist):
    """Check the points given, whether they are isolated.

    The source and max_dist helps in early termination of the check, by checking whether
    we have been far enough that it is impossible for walls to form.
    """
    def distance(point):
        return abs(point[0]-source[0]) + abs(point[1]-source[1])
    if len(points) == 0:
        return True
    for check_point in points:
        stacked = set()
        stack = []
        if check_point in stacked:
            continue
        stacked.add(check_point)
        stack.append(check_point)
        current_is_valid = False
        while len(stack) > 0:
            row, col = stack.pop()
            if (row == 0 or col == 0 or row == len(grid)-1 or col == len(grid[0])-1 or
                    distance((row, col)) >= max_dist):
                # From this check_point it is valid, check other points
                current_is_valid = True
                break
            cur_neighbors = []
            for new_row, new_col in neighbors(row, col):
                if grid[new_row][new_col] == 'O' or (new_row, new_col) in stacked:
                    # Skip selected points and points that are already in the stack
                    continue
                stacked.add((new_row, new_col))
                cur_neighbors.append((new_row, new_col))
            # Prioritize the furthest point from the origin
            cur_neighbors = sorted(cur_neighbors, key=distance)
            stack.extend(cur_neighbors)
        if not current_is_valid:
            return False
    return True

def simplify(structure):
    """Removes empty rows and columns, compacting the display
    """
    structure = structure[:]
    for i in range(len(structure)):
        structure[i] = list(''.join(structure[i]).replace('X', '.'))
    for row_idx in reversed(range(len(structure))):
        row = structure[row_idx]
        if len(row) == row.count('.'):
            # All empty, remove
            structure[row_idx:row_idx+1] = []
    for col_idx in reversed(range(len(structure[0]))):
        empty = True
        for row_idx in range(len(structure)):
            if structure[row_idx][col_idx] != '.':
                empty = False
                break
        if empty:
            for row in structure:
                row[col_idx:col_idx+1] = []
    return structure

def main():
    parser = ArgumentParser(description='Generate all possible floorplans')
    parser.add_argument('-n', type=int, help='The number of points')
    args = parser.parse_args()

    max_n = args.n

    with open(f'floorplans-{max_n}.txt', 'w') as outfile:
        for struct_id, structure in enumerate(generate_structures(max_n)):
            structure = simplify(structure)
            outfile.write(f'Structure ID: {struct_id}\n')
            outfile.write('\n'.join(''.join(row) for row in structure))
            outfile.write('\n\n')

if __name__ == '__main__':
    main()

---

For n=10, there are 39,425 different floorplans.

For n=5 it prints the following 63 structures:

Structure ID: 0
.O
.O
.O
OO

Structure ID: 1
.OO
.O.
OO.

Structure ID: 2
..O
.OO
OO.

Structure ID: 3
.OOO
OO..

Structure ID: 4
.O.
.OO
OO.

Structure ID: 5
..O
..O
OOO

Structure ID: 6
..OO
OOO.

Structure ID: 7
...O
OOOO

Structure ID: 8
OOOOO

Structure ID: 9
OOOO
...O

Structure ID: 10
OOO.
..OO

Structure ID: 11
OOO
..O
..O

Structure ID: 12
..O.
OOOO

Structure ID: 13
..O
OOO
..O

Structure ID: 14
OOOO
..O.

Structure ID: 15
OO..
.OOO

Structure ID: 16
OO.
.OO
..O

Structure ID: 17
OO
.O
OO

Structure ID: 18
OO.
.O.
.OO

Structure ID: 19
OO
.O
.O
.O

Structure ID: 20
OO.
.OO
.O.

Structure ID: 21
.O.
.O.
OOO

Structure ID: 22
.OO
OOO

Structure ID: 23
.O..
OOOO

Structure ID: 24
.O.
OOO
..O

Structure ID: 25
.O
.O
OO
.O

Structure ID: 26
.OO
OO.
.O.

Structure ID: 27
.O.
OO.
.OO

Structure ID: 28
.O
OO
.O
.O

Structure ID: 29
..O
OOO
.O.

Structure ID: 30
OOOO
.O..

Structure ID: 31
OOO
.OO

Structure ID: 32
OOO
.O.
.O.

Structure ID: 33
.O.
OOO
.O.

Structure ID: 34
O.O
OOO

Structure ID: 35
O...
OOOO

Structure ID: 36
O..
OOO
..O

Structure ID: 37
O..
OO.
.OO

Structure ID: 38
O.
OO
.O
.O

Structure ID: 39
O..
OOO
.O.

Structure ID: 40
O..
O..
OOO

Structure ID: 41
O.
O.
OO
.O

Structure ID: 42
O.
O.
O.
OO

Structure ID: 43
O
O
O
O
O

Structure ID: 44
O.
O.
OO
O.

Structure ID: 45
O..
OOO
O..

Structure ID: 46
O.
OO
OO

Structure ID: 47
O.
OO
O.
O.

Structure ID: 48
.O
.O
OO
O.

Structure ID: 49
.OO
OO.
O..

Structure ID: 50
..O
OOO
O..

Structure ID: 51
OOOO
O...

Structure ID: 52
OOO
O.O

Structure ID: 53
OO.
OOO

Structure ID: 54
OO
OO
.O

Structure ID: 55
OO
O.
OO

Structure ID: 56
OO
O.
O.
O.

Structure ID: 57
.O.
OOO
O..

Structure ID: 58
.O
OO
OO

Structure ID: 59
.O
OO
O.
O.

Structure ID: 60
OOO
OO.

Structure ID: 61
OOO
O..
O..

Structure ID: 62
OO
OO
O.

Answer 2

I am not sure to understand what you try to do, but I think that you can generate all shapes made of 10 points in the following way:

• start from an arbitrary pixel, mark it and try to move in the four cardinal directions;

• at the next pixel, mark it and try to move in the four cardinal directions, provided the pixels are unmarked;

• continue recursively until you reach the allowed number of pixels. If you reached a neighbor of the initial pixel, you have a valid shape;

• when recursion backtracks, unmark the pixel you are leaving.

If you don't want to have copies that are symmetric by a 90° rotation, it suffices to only make the first move in one direction.

As a probably useful optimization, you can avoid the paths that escape far from the initial pixel by avoiding a move such that a return will not possible (Manhattan distance too large).