0
$\begingroup$

Let’s say there are n fixed words permitted in some game of Scrabble, on an m x m squares board.

We are assuming an idealized scenario where anyone can write any word on the board. Assume both players have an unlimited number of every word. Or, assume there is only one player, playing every round.

Assume all the allowed words are the same length or shorter than the length of the board.

The number of choices for the first move will be, for each word, the number of positions on the board it can be placed. (I assume this is a subquestion with an easy answer.) (It must be placed on the starting central square).

After a word is lain on the table, maybe we have to calculate the number of choices for the next word just iteratively, where for each adjacent square to all pieces on the board, we count the number of valid scrabble words fitting there, bounded by the amount of available space.

Is it possible to prove what the highest possible scoring move across all possible games of Scrabble is?

Is this an easy problem, or does it suffer from combinatorial explosion?

What is the complexity class of such an algorithm?

$\endgroup$

1 Answer 1

0
$\begingroup$

Scrabble is PSPACE-Complete (see this ref.). Dynamic programming can be used to devise a more tractable solution instead of plain brute force.

Here are some pointers to designing an efficient Scrabble solution: some computer programs, a useful data structure called GADDAG, and a stackoverflow discussion.

$\endgroup$
1
  • $\begingroup$ The one-player variant described above is clearly in NP. $\endgroup$
    – Pål GD
    Commented Apr 26 at 13:06

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.