Genera percorsi su n * n griglia

Question

Ho griglia n*n, dove ad esempio n=10. Devo riempirlo con elementi in bianco e nero. Ogni elemento nero deve avere uno, due o tre vicini neri. Non è consentito contenere elementi neri con quattro o zero vicini.

Come devo costruire questo tipo di griglia?

Edit:

Per essere più specifici, è matrice bidimensionale costruito per esempio con due for loop:

n = 10 
array = [][]; 
for (x = 0; x < n; x++) { 
    for (y = 0; y < n; y++) { 
     array[x][y] = rand(black/white) 
    } 
} 

Questo codice pseudo costruisce somethind come:

E quello che mi aspetto è:

Answer 1

Ovviamente, stai cercando di generare forme "percorso nero" su una griglia di scrittura.

Quindi facciamolo.

• Inizia con una griglia bianca.
• Posiziona casualmente alcune tartarughe su di esso.
• Poi, mentre la griglia non soddisfa un corretto rapporto cellulare bianco/nero, effettuare le seguenti operazioni
  • spostare ogni tartaruga una cella in una direzione casuale e Paint It Black a meno che così facendo rompere il "non più di tre "vicini neri".

Answer 2

Con le dimensioni che si mostra qui, si potrebbe facilmente andare a fare un po 'di un'implementazione forza bruta.

Scrivere una funzione che controlla se si soddisfano i requisiti, semplicemente iterando attraverso tutte le celle e contando i vicini.

Dopo di che, fare qualcosa di simile:

Start out with a white grid. 
Then repeatedly: 
    pick a random cell 
    If the cell is white: 
     make it black 
     call the grid checking routine. 
     if the grid became invalid: 
      color it gray to make sure you don't try this one again 

do this until you think it took long enough, or there are no more white cells. 
then make all gray cells white. 

Se la vostra rete è di grandi dimensioni (migliaia di pixel), probabilmente si dovrebbe cercare un algoritmo più efficiente, ma per una griglia di 10x10 questo sarà calcolato in un flash.

Answer 3

Forse questo codice Python potrebbe essere di qualche utilità. La sua idea di base è di fare una sorta di prima traversata della griglia, assicurando che i pixel anneriti rispettino il vincolo di non avere più di 3 vicini neri. Il grafico corrispondente alla parte annerita della griglia è un albero, come sembrava il risultato desiderato.

import Queue 
import Image 
import numpy as np 
import random 

#size of the problem 
size = 50 

#grid initialization 
grid = np.zeros((size,size),dtype=np.uint8) 

#start at the center 
initpos = (size/2,size/2) 

#create the propagation queue 
qu = Queue.Queue() 

#queue the starting point 
qu.put((initpos,initpos)) 

#the starting point is queued 
grid[initpos] = 1 


#get the neighbouring grid cells from a position 
def get_neighbours(pos): 
    n1 = (pos[0]+1,pos[1] ) 
    n2 = (pos[0] ,pos[1]+1) 
    n3 = (pos[0]-1,pos[1] ) 
    n4 = (pos[0] ,pos[1]-1) 
    return [neigh for neigh in [n1,n2,n3,n4] 
        if neigh[0] > -1 and \ 
        neigh[0]<size and \ 
        neigh[1] > -1 and \ 
        neigh[1]<size \ 
     ] 


while(not qu.empty()): 
    #pop a new element from the queue 
    #pos is its position in the grid 
    #parent is the position of the cell which propagated this one 
    (pos,parent) = qu.get() 

    #get the neighbouring cells 
    neighbours = get_neighbours(pos) 

    #legend for grid values 
    #0 -> nothing 
    #1 -> stacked 
    #2 -> black 
    #3 -> white 

    #if any neighbouring cell is black, we could join two branches 
    has_black = False 
    for neigh in neighbours: 
    if neigh != parent and grid[neigh] == 2: 
     has_black = True 
     break 

    if has_black: 
    #blackening this cell means joining branches, abort 
    grid[pos] = 3 
    else: 
    #this cell does not join branches, blacken it 
    grid[pos] = 2 

    #select all valid neighbours for propagation 
    propag_candidates = [n for n in neighbours if n != parent and grid[n] == 0] 
    #shuffle to avoid deterministic patterns 
    random.shuffle(propag_candidates) 
    #propagate the first two neighbours 
    for neigh in propag_candidates[:2]: 
     #queue the neighbour 
     qu.put((neigh,pos)) 
     #mark it as queued 
     grid[neigh] = 1 

#render image 
np.putmask(grid,grid!=2,255) 
np.putmask(grid,grid<255,0) 
im = Image.fromarray(grid) 
im.save('data.png') 

Ecco il risultato impostazione size = 50

e un'altra impostazione size = 1000

Si può anche giocare con la radice dell'albero uno.