Fill char matrix with random words

Asked

Viewed 861 times

7

I’m trying to develop an algorithm that can get an array of strings, sort by word size downwards, and put them into a char matrix by fitting all the words together if possible. The idea of everything would be like creating a grid and having the words "connect" through letters in common, to draw the idea imagine a word search.

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 matrix 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 make this algorithm?

Thanks :)

algorithm matrix array char
  • 1

    What language?

  • @diegofm any one, but at first it would be Java

  • I think this problem requires a genetic algorithm. Spreading words becomes complicated as words that are already on the board may be occupying drawn spaces for the next.

  • @Celsomarigojr Some suggestion of algorithmism?

1 answer

1

That problem is NP-complete, you can use an algorithm Brute Force to solve it. It consists of trying all possibilities, and stopping when a possibility is a valid one. Will return failure when testing all possible solutions and finding none.

A solution using brute force is the Backtracking, look at 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 that link, has an algorithm ready in Python.

No stackoverflow in English has this question, I think it can be useful, because the language used is Java.

Browser other questions tagged algorithm matrix array char

You are not signed in. Login or sign up in order to post.