crossword - 生成所有独特的填字游戏网格

Question

我想生成特定网格大小(4x4 是一个很好的大小)的所有独特的填字游戏网格。所有可能的谜题，包括非唯一的谜题，都由一个具有网格区域长度(4x4的情况下为16)的二进制字符串表示，因此所有可能的4x4谜题都由0范围内所有数字的二进制形式表示到 2^16。

生成这些很容易，但我很好奇是否有人有一个好的解决方案来以编程方式消除无效和重复的案例。例如，所有具有单列或单行的谜题在功能上是相同的，因此消除了这 8 个案例中的 7 个。此外，根据填字游戏惯例，所有方块必须是连续的。我已经成功删除了所有重复的结构，但我的解决方案需要几分钟才能执行，而且可能并不理想。我对如何检测连续性感到茫然，所以如果有人对此有想法，我将不胜感激。

我更喜欢 python 中的解决方案，但用你喜欢的任何语言编写。如果有人愿意，我可以发布我的 python 代码来生成所有网格并删除重复项，尽管它可能很慢。

Answer 1

免责声明:除了所有测试确实通过过滤掉一些网格而产生影响之外，大部分未经测试，并且修复了一些发现的错误。当然可以优化。

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