0

Recently I came across an interesting Boogle solving algorithm problem. While I am familiar with the methods of solving it, I would now like to make a good letter generator for a Boogle board and am looking for an efficient algorithm to do so.
First two steps are straight-forward:

1) Boogle board is 5x5, so I will have an array of 25 chars. Randomly generate an array of 25 chars.
2) Shuffle the array obtained in the step 1

What next? I need to optimize the obtained array to be able to get as many meaningful words as possible. One thing that comes to mind is discarding all combinations of three same letters in a row. Example: [b b b a c c] is not quite good. Or should I just limit every letter to appear max twice?

Also, when generating numbers, the letters would have to be weighted. Example, we don't a lot of X and Ys, but vowels can appear many times.

Anything else?

Any guidelines are welcome.

Community
  • 1
  • 1
Maggie
  • 7,823
  • 7
  • 45
  • 66
  • 2
    Why are you shuffling the array if you randomly generated it? Isn't that redundant? – Bernhard Barker Jan 17 '14 at 07:15
  • Check out http://stackoverflow.com/questions/19456295/how-to-generate-board-for-game-like-boggle - and shuffling the array is definitely redundant when randomly generating it. – Martol1ni Jan 17 '14 at 07:24
  • This isn't a well-defined problem. If you just want one with lots of words, generate multiple grids and pick the one with the most words in it. – Paul Hankin Jan 17 '14 at 07:25
  • Note that Boggle uses a **4x4** grid. – AakashM Jan 17 '14 at 10:01

2 Answers2

0

Look at the Markov's chains and n-grams (I think, digrams are suitable for this problem) to generate letter combinations with high probability of word appearance

MBo
  • 77,366
  • 5
  • 53
  • 86
0

Any sort of non-dictionary-based board generator would run the risk of containing little to no actual words.

To address this, this fairly simple (at least on the high level) approach comes to mind:

  • Have a dictionary of allowable words.

  • Repeatedly randomly pick an unpicked word from the dictionary (if you're going to pick a large percentage of the words, shuffling would help you do this efficiently, otherwise you can just maintain a set of the already-picked words - this is assuming you actually don't want duplicate words on the same board), and do the following with that word:

    • Pick a random open cell on the board. This would be the location of the first letter of the word.

    • Repeatedly go in a random direction (to an open cell) for the next letter. If one of the neighbouring cells contains the next letter already, we could go to that cell instead. If you run into a scenario where no directions work, backtrack and pick a different direction to a previous letter.

You could perhaps eliminate cells from being repicked if you picked it and couldn't manage to form a word. You could also eliminate all cells you visited during the process to assign cells for that word. Although this is not perfect - if you couldn't fit a 10-letter word, that doesn't mean a 3-letter word won't work.

You'd obviously stop either when the board is mostly full or you have some number of words on the board already.

This still leaves a lot open to the implementation, but it's just meant to be a high-level idea.

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138