I’ve been Scrabbling by email lately. In today’s game my partner started out by playing
H
E
X
and I responded with
A H
W E
E X
At this point my opponent might well have continued with another three-letter word to make a tidy square block such as:
Y A H
E W E
S E X
In actuality she did something quite different. She played a seven-letter “bingo,” using all her letters to earn a 50-point bonus; as a result I’m hopelessly far behind in the scoring. But let us say no more about the tawdry details of winning and losing; there’s a puzzle here. Looking at that three-by-three block of letters and words, it occurs to me there must surely be legally reachable configurations of a Scrabble board that have no legal continuation. Scrabble rules say that, except for the first move, letters can be added to the board only on squares adjacent to existing letters, and all sequences of two or more letters (both vertically and horizontally) must be dictionary words. The rules say nothing about the situation where continued play is impossible.
I’m sure there must be many stymied positions, where no words can be formed, regardless of what letters you have on your rack. Or so I assert; but, the fact is, I haven’t been able to find even one such configuration. A cursory examination of the list of all allowed two-letter words argues that no two-by-two block of letters can be stymied. What about two-by-three or three-by-three blocks? Somebody must have settled these questions, but my Googling has failed to find the answer. What is the smallest stymied position? (I don’t require that a solution be a rectangular block of letters, but having stray letters dangling off the edges of a block makes it easier rather than harder to form words.)
No 3×3 block can be a terminal position.
I took the SOWPODS list and ran it through a perl script looking for words which cannot be extended to longer legal words. The only way to get a 3×3 block which cannot be played upon is if none of the 9 words can be extended to 4 or more letters.
Alas, there are only 5 words of length 3 that are not stems:
SWY
FAP
TWP
VLY
QIS
Obviously these cannot be assembled into a 3×3 block. (There are no nonextendable words of length two.)
Any 4×3 block would have to contain four of these words along the short dimension (not necessarily unique) which doesn’t look possible.
There are 250 such words of length 4, leading to a search space of about 4 billion possibilities. Might be feasible.
Could something smaller than a 4×4 block be terminal? Perhaps something like this
xx
xxxx
xxxx
xx
would work if the 2-letter runs did not have a common letter in their extensions.
That figure should be
oxxo
xxxx
xxxx
oxxo
This approach doesn’t take letter frequencies into account. There might be a position which has words that can be extended, but only via letters already used up. (But for small positions the blank would probably allow play.)
Here are the 4×4 blocks that are not extensible. Note that they are all symmetric.
GJUS
JIVY
UVAE
SYED
THEY
HIYA
EYRY
YAYS
TECS
ELHI
CHEZ
SIZY
I think the middle one is actually reachable via legal play, excepct that it has 6 occurences of ‘Y’. The other two look hopeless as well.
Thanks, Mark! Very impressive.
Mark, yes, I found the same three 4×4 grids and came to the same conclusions. Alas, I don’t think any of them can arise in legal play. I’ll hunt for simple move sequences that generate stymied 5×5 grids.
Your comment about words that cannot be extended because the necessary letters have already been used is very interesting. It makes the search significantly more complex, even for 4×4 grids, since in theory any word could be involved. It’s unlikely, but it might even produce a stymied 3×3 grid!
Come to think of it, it might be easier to generate a stymied position at the end of a game rather than the beginning. Let’s just imagine playing out 98 tiles, leaving each player with a single V and nowhere to place it. I expect it would be pretty easy to construct such a board, though I’d be the first to admit that it’s much more boring as a stymied position than a minimal grid on an otherwise empty board.
Another note — the rules don’t say anything explicit about what to do when continued play is impossible. But players always have the option of passing. I found one site that says that the game ends if everyone passes twice in a row. Hasbro (and my physical Scrabble game) says “The game ends when all letters have been drawn and one player uses his or her last letter; or when all possible plays have been made,” which could be taken to include stymied positions.
Mark Gritter writes “I think the middle one is actually reachable via legal play.” Here’s one way to do it, making use of the SOWPODS intermediates HEY, HI, and YA:
My apologies if the columns don’t line up well (I hope Brian will fix it so they do).
I’ll try that again, in case it’s so obscure even Brian can’t figure out what I meant:
*HEY
****
****
****
*HEY
**Y*
**R*
**Y*
*HEY
HIYA
**R*
**Y*
THEY
HIYA
E*R*
Y*Y*
THEY
HIYA
E*R*
YAYS
THEY
HIYA
EYRY
YAYS
(I was trying to use -’s for empty squares and run all the steps across one “line” in the first attempt, but the wordprocessing here seems to ignore repeated space bar entries, and interprets multiple -’s in some weird way.)
An anonymous commenter on my blog offers this legal path to another one of the 4×4 blocks, so we do have a good bound of 16 tiles. This requires the use of one of the blank tiles for ‘J’.
GJUS
GJUS
*I**
*V**
*Y**
GJUS
*I**
*V**
SYED
GJUS
*I*Y
*V*E
SYED
GJUS
*I*Y
UVAE
SYED
GJUS
JIVY
UVAE
SYED
Here is the legal construction of the last block:
TECS
****
****
****
TECS
E***
C***
S***
TECS
E*H*
C*E*
S*Z*
TECS
E*H*
C*E*
SIZY
TECS
ELHI
C*E*
SIZY
TECS
ELHI
CHEZ
SIZY