java - How to split a 2D array in different sized pieces for a crossword? -

i experimenting generator crossword puzzle getting stuck when time split different pieces. have 2d array store crossword this:

int size = 10; //this can higher bigger crosswords character[][] crossword = new character[size][size]; 

i add few words crossword , example end following array (. = empty square):

.......... .......... ..c...h... ..a...o... ..tiger... ......s... ...dove... .......... .......... .......... 

how split 2d array end pieces contains @ least 2 letters not whole word. letters must next each other horizontally or vertically not diagonally. example end following pieces:

c    tig    h    er    dov           o     s                   e 

the following piece not valid because letters not horizontally or vertically next eachother.

  o ge   s 

my first atempt split doing following:

int chunksize = 2; //this should vary depending on how big pieces should list<character[][]> subarrays = new arraylist<>(); for(int = 0; < size; += chunksize){     for(int j = 0; j < size; j += chunksize){         character[][] sub = new character[chunksize][chunksize];         sub[0][0] = crossword[i][j];         sub[0][1] = crossword[i][j + 1];         sub[1][0] = crossword[i + 1][j];         sub[1][1] = crossword[i + 1][j + 1];         if(sub[0][0] != null || sub[0][1] != null || sub[1][0] != null || sub[1][1] != null){             subarrays.add(sub);         }     } } 

however, might create pieces contains 1 letter or pieces letters not next each other. not know how should solve problem why come here help.

domino packing

the following approach creates many size-2 blocks possible. afterwards, remaining individual letters need attached neighbouring block somehow -- e.g., picking 1 of neighbouring blocks @ random.

create graph vertex each position occupied letter, , edge between pair of vertically or horizontally adjacent letter positions. compute maximum matching on graph: chooses maximum-size edge subset such no vertex incident on more 1 edge. these edges correspond size-2 blocks.

if imagine grid chessboard, you'll notice every square either white or black, , no edge connects 2 white cells or 2 black cells: means graph bipartite, in turn means can use o(|e|*sqrt(|v|))-time hopcroft-karp algorithm, faster , simpler edmonds's algorithm general graphs.