Генерация всех уникальных сеток кроссвордов - PullRequest
Новая
       16

Генерация всех уникальных сеток кроссвордов

3 голосов
/ 14 мая 2010

Я хочу сгенерировать все уникальные сетки кроссвордов определенного размера (4x4 - хороший размер). Все возможные головоломки, включая неуникальные головоломки, представлены двоичной строкой с длиной области сетки (16 в случае 4x4), поэтому все возможные головоломки 4x4 представлены двоичными формами всех чисел в диапазоне 0 до 2 ^ 16.

Создать их легко, но мне любопытно, есть ли у кого-нибудь хорошее решение для того, как программно устранить недопустимые и повторяющиеся случаи. Например, все головоломки с одним столбцом или одной строкой функционально идентичны, что исключает 7 из этих 8 случаев. Кроме того, согласно соглашениям кроссвордов, все квадраты должны быть смежными. Я успешно удалил все дублирующиеся структуры, но мое решение заняло несколько минут и, вероятно, не было идеальным. Я в некотором затруднении из-за того, как обнаружить смежность, поэтому, если у кого-то есть идеи по этому поводу, это будет высоко ценится.

Я бы предпочел решения на python, но пишу на любом языке, который вы предпочитаете. Если кто-то захочет, я могу опубликовать свой код на Python для генерации всех сеток и удаления дубликатов, как бы медленно это ни было.

1 Ответ

3 голосов
/ 14 мая 2010

Отказ от ответственности: в большинстве случаев непроверенные, кроме всех тестов do оказывают влияние, отфильтровывая некоторые сетки, и исправлены некоторые обнаруженные ошибки. Конечно, можно оптимизировать. 

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
...