I find it somewhat interesting to try to get these things exact (or try to
analyze the hell out of it)
I've seen it written that the name of the topic relating to the number of
possible connected board combinations is 'polyominoes'.
Is every configuration of 100 connected squares achievable, given the standard
English starting pool and one of the standard lexicons? It seems possible some
weird configurations might not be achievable (say if it is 15 letter words
connecting in some un-fortuitous combination.)
In counting the possible games I would want to consider two games different if
the racks were different. A starting play of QI from a rack of QIABCDE is
different from a starting play of QI from QUIETER for example. The final board
layout may be the same but the experience of the game can be very different if
the racks are different.
I have counted the exact number of racks from the standard starting pool and
the answer I have in front of me is 2,665,920.
For example how many racks have 7 different tiles?
27 choose 7 is 888,030.
How many have 1 duplicate pair, and 5 additional different tiles?
22 (excluding XKJQZ) * (26 remaining choices, choose 5) = 1,447,160
Some slightly complicated cases
A set of 4, a pair, and 1 more tile not matching them
{A,E,I,O,N,R,T,D,L,S,U}=11
11 * (22-1) * (27-2) = 11 * 21 * 25 = 5,775
Three pairs and a singleton
(22 choose 3) * (27 - 3) = 36,960
The spreadsheet I used has all 15 distinct ways of breaking down the number 7
into sums of positive integers, so I think I probably got the total right
In breaking up a rack of N tiles into groups of similar tiles - extensive
research is available here:
http://www.research.att.com/~njas/sequences/A000041
When the pool is diminished, the possibilities decrease.
There must be some statistical methods usable to achieve some pretty strong
bounds on the number of possible games, probabilistically, in lieu of
enumerating all the games.
For example assume the number of exchanges per player in a game is 1.0 on
average, distributed binomially or something simple like that.
Assume the tiles are connected 99.9% of the time. Figure out the average
number of moves available and standard deviations, given that there are N tiles
on the board already. Assume independence and go from there.
In considering board configurations alone watch out to consider the score is
important, so how the board configuration is achieved is important too of
course.
Another silly idea is to use distributed computing like s...@home to use
people's spare CPU cycles to work on enumerating scrabble positions
Kevin Leeds
