2

特定のグリッド サイズ (4x4 が適切なサイズ) のすべてのユニークなクロスワード パズル グリッドを生成したいと考えています。一意でないパズルを含むすべての可能なパズルは、グリッド領域の長さ (4x4 の場合は 16) のバイナリ文字列で表されるため、可能なすべての 4x4 パズルは範囲 0 のすべての数値のバイナリ形式で表されます。 2^16 に。

これらを生成するのは簡単ですが、無効で重複したケースをプログラムで排除する方法について誰かが良い解決策を持っているかどうか知りたいです. たとえば、1 つの列または 1 つの行のすべてのパズルは機能的に同一であるため、これら 8 つのケースのうち 7 つが除外されます。また、クロスワード パズルの規則に従って、すべての正方形が連続している必要があります。重複した構造をすべて削除することに成功しましたが、私のソリューションの実行には数分かかり、おそらく理想的ではありませんでした。隣接性を検出する方法に途方に暮れているので、誰かがこれについてアイデアを持っているなら、それは大歓迎です。

私はPythonでのソリューションを好みますが、好きな言語で書いてください。必要に応じて、すべてのグリッドを生成し、重複を削除するための Python コードを投稿できますが、遅いかもしれません。

4

1 に答える 1

3

免責事項: すべてのテスト以外はほとんどテストされていませんが、いくつかのグリッドを除外することで影響があり、いくつかの発見されたエラーが修正されました。確かに最適化できます。

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
于 2010-05-14T18:19:38.873 に答える