So there is the question of how many ways can you fit 99 tiles versus how many possible scrabble games...
We could probably eliminate a lot positions as being highly unlikely... Like almost any big chunk of tiles in quadrilateral 10x10 or 6x15 etc. I am guessing we could generalize from a small 5x5 grid and 3 tiles. Then expand that out. The answer is a lot, but not that much. --- On Fri, 3/6/09, Kevin Leeds <[email protected]> wrote: From: Kevin Leeds <[email protected]> Subject: [quackle] Re: Scrabble Complexity To: [email protected] Date: Friday, March 6, 2009, 5:20 PM 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
