Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I recently saw a question on SO about solving the scramble/boggle game, where the letters are in a 4x4 grid and you have to find as many words as possible. I looked at some of the solutions, tried it myself, and would now like to move onto solving a scrabble game.

The boggle solving code is rather simple; store the board state in a matrix and iterate over every move from every position and checking if words exist with the current letter chain.

With scrabble, the idea is similar, but I'm still having trouble figuring it out. My currently thinking of:

  1. Storing the board in 2 dimensional array.
  2. Iterating over each position and skipping if the position is empty.
  3. Creating some sort of regex pattern for the letters on the rack and the letter at the position...

I'm still really iffy on what to do at step 3 because I know the tile at the position could be the beginning end, or some point in the middle of a word. And then there's the matter of making sure that if a word does fit that it also makes words with other tiles it touches..

I'm not asking for code samples, just the thought process from more experienced programmers.

To clarify, my goal is:

Given the current state of a board and a person's tiles, calculate the legal moves and the points for that move.

For anyone following this and waiting for an answer, I found this: http://www.chaddington.com/portfolio/project.html#scrabble

I might look through what he wrote, but I do want to try to figure it out myself first.

share|improve this question
    
Is the methodology tag really appropriate here? I tried changing it to algorithms but without success. –  mmyers Feb 1 '12 at 14:48

1 Answer 1

up vote 4 down vote accepted

I believe you've forgotten the question itself. What is your intent?

  • Given a Scrabble board with already filled tiles, find all the words available?
  • Or let the users play Scrabble by adding tiles and check the score with every newly added tile?

If it's the first point, then you may want to:

  1. Transform your board into a set of 30 uni-dimensional arrays: one containing rows, another - the columns.

  2. For every row, walk through the tiles in the row, surrounding the row by whitespace (empty tiles) and then, replacing consecutive whitespace (empty tiles). For example, "····stack··meta" would become "·stack·meta".

  3. Split those into words. "·stack·meta" would be ("stack", "meta").

  4. Check each word against a dictionary.


If it's the second point, then you don't have to "iterate over each position" (point 2 in your list). You simply search for the words from a given position Ca, b :

  • Horizontally, starting from Ca, 1 and walking to the right until Ca, 15,
  • Vertically, starting from C1, b and walking to the bottom until C15, b.

To simplify, you can create two uni-dimensional arrays as:

  • A₁(a) → Ca, n, 1 ≤ n ≤ 15
  • A₂(b) → Cn, b, 1 ≤ n ≤ 15

Then you'll have to create a single method which will determine existent words given:

  • An uni-dimensional array (A₁ or A₂),
  • A one-dimension position of the current tile in the array.

How? I would start by isolating the word itself, i.e. find the previous and the next whitespace (i.e. empty tile), if any. Then a formed word must be checked against a dictionary. Then you count the score, taking in account the colors of tiles and the tile characters.

Example (using a syntax of an imaginary language):

var A₁ = " stack overflow".ToArray(); // Given the one-dimension array...
var b = 4; // ... and the position of the current tile...
var leftEdge = A₁.Take(b).FindLast(' '); // Find the left empty tile,
var rightEdge = A₁.Skip(b).FindFirst(' '); // Then the right empty tile,
var word = A₁.Subset(leftEdge + 1, b + rightEdge - 1); // Then extract the word itself.
Assert.AreEquals("stack", word); // Found a good one?
bool isValidWord = word.IsInDictionary("en-US"); // Search the word in the dictionary.
Assert.IsTrue(isValidWord); // "stack" is a valid word.
share|improve this answer
    
No, it was the first point. Given the current state of a board and a person's tiles, calculate the legal moves and the points for that move. –  mowwwalker Feb 1 '12 at 0:56
    
@user828584: I see. Edited. –  MainMa Feb 1 '12 at 1:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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