La generazione di tutte le unico cruciverba griglie

Question

Voglio generare tutti unici cruciverba reti di una certa dimensione della griglia (4x4 è una buona dimensione).Tutti i possibili puzzle, tra cui camere non-puzzle unici, sono rappresentati da una stringa binaria di lunghezza della griglia (16 nel caso di 4x4), così tutti i possibili 4x4 puzzle sono rappresentati dalla forma binaria di tutti i numeri nell'intervallo da 0 a 2^16.

La generazione di questi è facile, ma io sono curioso di sapere se qualcuno ha una buona soluzione per come a livello di eliminare le voci e i casi duplicati.Per esempio, tutti i puzzle con una singola colonna o riga singola che sono funzionalmente identici, quindi eliminando 7 di coloro 8 casi.Inoltre, secondo il cruciverba convenzioni, tutte le piazze devono essere contigui.Ho avuto successo la rimozione di tutti i duplicati di strutture, ma la mia soluzione sono voluti diversi minuti per eseguire e, probabilmente, non era l'ideale.Io sto a qualcosa di una perdita per come rilevare contiguità quindi, se qualcuno ha idee su questo sarebbe molto apprezzato.

Io preferirei soluzioni in python, ma scrivere in qualsiasi lingua che si preferisce.Se qualcuno vuole, mi può postare il mio codice python per la generazione di tutte le griglie e la rimozione dei duplicati, lento come potrebbe essere.

Answer 1

Disclaimer:soprattutto non testati diversa da tutte le prove fare hanno un impatto filtrando alcune griglie e un paio di errori individuati sono stati risolti.Può certamente essere ottimizzato.

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