2

I am looking for an algorithm able to build an array (2D) of letters from which I could extract each word of a given list. Like in Scrabble, words can cross each other, and be horizontal, vertical or diagonal. Of course there are some obvious solutions, but the goal here is to make it as small as possible, which also means maximizing the number of crossing.

I have thought of a machine learning method using a large set of scrabble grids, either made by humans or computers, but I am sure there is a cleaner way of doing it.

Thanks for your help.

PS: that is for an art project, no kidding.

3
  • 1
    Finding the minimal solution will be extremely difficult. Can't you just settle for a good solution, rather than an optimal one? Regarding "which also means maximizing the number of crossing": this is not a true statement. Maximizing the number of crossings is a very similar problem, but the optimal result for these two problems will be different in many cases.
    – Mark Byers
    Apr 11, 2012 at 14:19
  • Thanks guys, and sorry for being not precise enough. A good solution would be enough, for sure finding the absolute optimal would be hell. Also, thanks for highlighting that it's not the same problem as optimizing crossing. I totally agree, I was meanin "those problems seem to be close".
    – aymeric l
    Apr 11, 2012 at 15:54
  • 1
    (scoring) words in scrabble are not diagonal. May 3, 2012 at 9:03

1 Answer 1

0

That would be quite some algorithm. I suspect the solution will involve some sort of recursion.

Let's say you have a grid G0 to start with, with all squares blank, and that f(G0) is the optimised completed grid.

Then I would try:

For each possible position of the first word - set G1 = the grid with this word in this position and all other squares blank - work out G1 Go on to next position

To work out G1, you could call f(G1) recursively.

If you had a large grid and a lot of words, this would take forever to run, as it's a wasteful algorithm, but with a typical Scrabble board I should think it would be quick enough on a laptop.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.