Home‎ > ‎Luc‎ > ‎Software Applications‎ > ‎

ScrabbleScore

This is an application to solve a Scrabble board, given the existing words on the board, the tray of letters contained, and a dictionary of words.

This project was one that took me about 3 months to complete. A lot of thought went into creating this application. There is about 3000 lines of code. The application works great, except for the single fact that the mass of the calculation are repeated for each iteration, which proves to be quite painful since it takes about 2.5 hours to solve for the best word on the board, which really does suck. There are versions out there which build up a database initially, and then look up on that every time, taking only about 5 seconds per play.

This game requires three main things to start off.

1) An existing board configuration (may be empty)
2) Tray of letters that the player currently has, including wildcards
3) A dictionary of words (in our case SOWPODS, the official scrabble dictionary, is used)

The program will take all of this information, and start trying words onto the existing board, which conform to the tray of available letters and based on the dictionary.

When loading a dictionary into the program, the words are considered as objects in Java, and therefore can be pointed to. So if there are x words in the dictionary, there are only x objects of words, but there may be 300x pointers to words. The way the words are categorized is as follows. A 3 dimensional array is formed. The columns consist of letters, A to Z. The rows represent where in the word the letter is in the word, and the depth of the array just contains all the words in that category. So you it can be looked as bins of words, but in programming language is a linked list of conforming words. It can be displayed as follows:

    A   B         Y   Z
  --------- ... ---------
  |   |   |     |   |   |
1 |   |   |     |   |   |
  |   |   |     |   |   |
  --------- ... ---------
  |   |   |     |   |   |
2 |   |   |     |   |   |
  |   |   |     |   |   |
  --------- ... ---------
  .   .   . ... .   .   .
  .   .   . ... .   .   .
  .   .   . ... .   .   .
  --------- ... ---------
  |   |   |     |   |   |
14|   |   |     |   |   |
  |   |   |     |   |   |
  --------- ... ---------
  |   |   |     |   |   |
15|   |   |     |   |   |
  |   |   |     |   |   |
  --------- ... ---------

So for example, the word "bob" would go in that database 3 times. Once in row 1, column 2, once in row 3, column 2, and once in row 2, column 15. (b, b, o)

By categorizing them this way, lookups are easy. If the word "light" is on the board, and it is near one of the edges of the board for example, we can limit our searches in the database. Lets say that the word light is horizontal on the board, and starts in the bottom left corner. So, we know that words that will use the word "light" must end at the bottom row, so we can limit our search to n letter words where the letter in light is placed at the n position (the last position).

Also, care must be taken when placing words adjacent to others. Many points can be obtained by doing so, but it takes a lot of computation in order to place such a word.

I won't describe all the algorithms, but the source code is available for viewing, considering that this project is licensed under the GPL. The javadoc should be contained in the package as well.

Please view the sourceforge scrabbleScore page for downloads.
Comments