Fill char array with random words [closed]

7

I'm trying to develop an algorithm able to get a vector of strings, sort by word size in descending order and place them inside an array of char embedding if possible all words. The idea of everything would be how to create a grid and make the words "connect" through letters in common, to draw the idea imagine a word-hunter.

Ex:

String[] palavras = new String[]{"vidro", "plastico", "amarelo", "madeira", "metal"};

palavras = OrdernarPorTamanho(palavras, DECRESCENTE);


char[][] grid = new char[15][15];

for(int linha = 0; linha < 15; linha++)
{
    for(int coluna = 0; coluna < 15; coluna++)
    {
       // Aqui viria as verificações para colocar todas as palavras do vetor dentro da matriz
    }
}

My desired output from the array would be as follows:

Ex:

- P L A S T I C O - - - - - -
- - - M E T A L - - - - - - -
- - - A - - - - - - - - - - -
- - - R - - - - - - - - - - -
M A D E I R A - - - - - - - -
- - - L - - - - - - - - - - -
- - - O R D I V - - - - - - -
- - - - - - - - - - - - - - -
- - - - - - - - - - - - - - -
- - - - - - - - - - - - - - -
- - - - - - - - - - - - - - -
- - - - - - - - - - - - - - -
- - - - - - - - - - - - - - -
- - - - - - - - - - - - - - -
- - - - - - - - - - - - - - -

Does anyone have any suggestions on how to do this algorithm?

Thanks:)

    
asked by anonymous 20.09.2016 / 12:52

1 answer

1

This problem is NP-complete , you can use an algorithm Força Bruta to solve it. It consists of trying all possibilities, and stopping when a possibility is a valid one. It will return failure when testing all possible solutions and find none.

One solution using brute force is the Backtracking , see this pseudocode:

solve(words,grid):
   if words is empty:
       if grid.isValudSol():
          return grid
       else:
          return None
   for each word in words:
       possibleSol <- grid.fillFirst(word)
       ret <- solve(words\{word},possibleSol)
       if (ret != None):
          return ret
   return None

In this link , you have an algorithm ready in Python .

In stackoverflow in English you have this question , I think it can be useful because the language used is Java .

    
22.09.2016 / 14:48