Generating all unique crossword puzzle grids

Question

I want to generate all unique crossword puzzle grids of a certain grid size (4x4 is a good size). All possible puzzles, including non-unique puzzles, are represented by a binary string with the length of the grid area (16 in the case of 4x4), so all possible 4x4 puzzles are represented by the binary forms of all numbers in the range 0 to 2^16.

Generating these is easy, but I'm curious if anyone has a good solution for how to programmatically eliminate invalid and duplicate cases. For example, all puzzles with a single column or single row are functionally identical, hence eliminating 7 of those 8 cases. Also, according to crossword puzzle conventions, all squares must be contiguous. I've had success removing all duplicate structures, but my solution took several minutes to execute and probably was not ideal. I'm at something of a loss for how to detect contiguity so if anyone has ideas on this it'd be much appreciated.

I'd prefer solutions in python but write in whichever language you prefer. If anyone wants, I can post my python code for generating all grids and removing duplicates, slow as it may be.

Answer 1

Disclaimer: mostly untested other than all tests do have an impact by filtering out some grids and a few spotted errors were fixed. Can certainly be optimized.

def is_valid_grid (n):
    row_mask = ((1 << n) - 1)
    top_row  = row_mask << n * (n - 1)

    left_column  = 0
    right_column = 0

    for row in range (n):
        left_column  |= (1 << (n - 1)) << row * n
        right_column |= 1 << row * n

    def neighborhood (grid):
        return (((grid   & ~left_column)  << 1)
                | ((grid & ~right_column) >> 1)
                | ((grid & ~top_row)      << n)
                | (grid                   >> n))

    def is_contiguous (grid):
        # Start with a single bit and expand with neighbors as long as
        # possible.  If we arrive at the starting grid then it is
        # contiguous, else not.
        part = (grid ^ (grid & (grid - 1)))
        while True:
            expanded = (part | (neighborhood (part) & grid))
            if expanded != part:
                part = expanded
            else:
                break

        return part == grid

    def flip_y (grid):
        rows = []
        for k in range (n):
            rows.append (grid & row_mask)
            grid >>= n

        for row in rows:
            grid = (grid << n) | row

        return grid

    def rotate (grid):
        rotated = 0
        for x in range (n):
            for y in range (n):
                if grid & (1 << (n * y + x)):
                    rotated |= (1 << (n * x + (n - 1 - y)))

        return rotated

    def transform (grid):
        yield flip_y (grid)

        for k in range (3):
            grid = rotate (grid)
            yield grid
            yield flip_y (grid)

    def do_is_valid_grid (grid):
        # Any square in the topmost row?
        if not (grid & top_row):
            return False

        # Any square in the leftmost column?
        if not (grid & left_column):
            return False

        # Is contiguous?
        if not is_contiguous (grid):
            return False

        # Of all transformations, we pick only that which gives the
        # smallest number.
        for transformation in transform (grid):
            # A transformation can produce a grid without a square in the topmost row and/or leftmost column.
            while not (transformation & top_row):
                transformation <<= n

            while not (transformation & left_column):
                transformation <<= 1

            if transformation < grid:
                return False

        return True

    return do_is_valid_grid

def valid_grids (n):
    do_is_valid_grid = is_valid_grid (n)
    for grid in range (2 ** (n * n)):
        if do_is_valid_grid (grid):
            yield grid

for grid in valid_grids (4):
    print grid