18
$\begingroup$

Consider the following Scrabble board:

enter image description here

We can play NO for 1 point, AI for 2 points, NOSE for 3 points etc as indicated on the right. All this obviously depends on having the correct letters on your rack (not shown). Eventually we will reach a number N such that it is impossible to score exactly N points on our next turn.

Let us say the "smallest unattainable score" of a game-state is the smallest positive number N such that we cannot score exactly N points on our next turn. The game-state includes both our rack and the board (we ignore the opponent's rack for simplicity). Can you construct a game-state with the largest smallest unattainable score?

Assume that the CSW19 dictionary is being used.

EDIT: The game state must be reachable by valid plays (no phonies)

For partial credit: to simplify the problem assume that the board state contains only one word.

SOURCE: The Scrabble board was cut-n-pasted from Wikipedia.

Thanks to FlanMan for a recent Scrabble-related question

$\endgroup$
6
  • 2
    $\begingroup$ Does the game state have to have a valid history? e.g. if this was a game state: imgur.com/FTB2L6b If "SOFT" was the last word played, "NCE" would've previously on the board, which is not a valid word. etc. So there is no valid 'previous history' $\endgroup$
    – thesilican
    Commented Aug 2, 2020 at 18:39
  • $\begingroup$ How is "NO" worth just 1 point? 1 for the N and 1 for the O, making 2, right? Or are we using a blank for the O? $\endgroup$
    – JLee
    Commented Jun 1, 2022 at 14:40
  • 1
    $\begingroup$ @JLee the N inside a square is a blank. I've seen this convention used when annotating actual games. $\endgroup$
    – happystar
    Commented Jul 25, 2022 at 4:09
  • $\begingroup$ I got curious about the algorithmic complexity of this problem: There are 4,114,349 scrabble racks according to this video. There are probably more than 50,000 words with 7 letters or fewer. Meaning even the simplified version has 200 billion things to check (naively). Oh there’s also the 2 to 7 different positions of the first word. Still, it’s an interesting problem. Some pruning methods: assume we have two blanks; assume the opponent played a 7-letter word; etc $\endgroup$ Commented Aug 20, 2023 at 21:05
  • 1
    $\begingroup$ Fluorine, my question is intended as a contest: highest SUS wins and you don't have to prove SUS+1 is impossible. In future I will probably try to avoid such problems since this is probably more suitable for e.g. programming contests $\endgroup$
    – happystar
    Commented Apr 24 at 21:56

2 Answers 2

8
+500
$\begingroup$

SUS = 174

JUXTAPOSE has {D, R} hooks.
PSYCHOANALYZE and QUADRILLE both have {D, R, S} hooks.

PSYCHOANALYZE does most of the work here. Its tiles contribute 105 points when a play passes through O8.

enter image description here

[x2373]  1  1M (E)a
[x7700]  2  1J aa
[x8765]  3  1I bAa
[x10631] 4  1I abA
[x12088] 5  1I aMa
[x11236] 6  1I iDE
[x8766]  7  1I aMA
[x8647]  8  1H aSEa
[x5387]  9  1H alAE
[x7373] 10  1I arEA(E)
[x5633] 11  1G cAESe
[x8443] 12  1G abASE
[x5242] 13  1I aSiD(E)
[x7435] 14  1G cADEe
[x4462] 15  1G alDEA
[x4763] 16  1H pESAd(E)
[x3025] 17  1F pESADe
[x3333] 18  1F mEDuSA
[x1686] 19  1H bEDAz(E)
[x2244] 20  1F cAMESe
[x1240] 21  1F aShAME
[x1908] 22  1H bEDAz(E)S
[x1502] 23  1F rEADMe
[x1355] 24  1F coMADE
[x 547] 25  1G SiAMEz(E)
[x 904] 26  1H MEdiA(E)
[x 406] 27  1F MEDuSA
[x 643] 28  1G bEDMAt(E)
[x 705] 29  1H bEjAD(E)
[x 555] 30 13J aMASs
[x 997] 31  1G sEASiD(E)
[x 819] 32  1G rESpAD(E)
[x 603] 33  1K aM(E)bA
[x 482] 34  1H dEMoD(E)
[x 494] 35  1H coMAD(E)
[x1161] 36  1H sESaM(E)
[x 669] 37  1H aShAM(E)
[x 177] 38  1G liMEAD(E)
[x 374] 39  1G wAESoM(E)
[x 293] 40  1G bEShAM(E)
[x 163] 41  1H rEMAD(E)S
[x 306] 42  1G EDAmaM(E)
[x 154] 43  1G acADEM(E)
[x 296] 44 13G A(L)DosES
[x 114] 45  O1 aMAS
[x 109] 46  1H DEfAM(E)S
[x 110] 47  O1 abASED
[x  75] 48 13G a(L)MuDES
[x 206] 49  O1 aSiDE
[x  50] 50 13G A(L)MnErS
[x  10] 51  O1 rEADdS
[x  78] 52 13G A(L)MonDS
[x  25] 53  O1 aMuSED
[x  16] 54 13G A(L)MuDES
[x  22] 55  O1 aMiDE
[x   5] 56  O1 AMuSED
[x  13] 57 15H d
[x  39] 58 15G ed
[x   2] 59  C4 ADMa(S)sES
[x  12] 60  C4 aDMA(S)sES
[x  32] 61 10B ADMirE(R)S
[x  97] 62 15G Ed
[x  61] 63 10B jEMaDA(R)S
[x  92] 64 13D MEDu(L)lAS
[x 172] 65 10B AMenDE(R)S
[x  45] 66 15E AbEd
[x 216] 67 10B MiDyEA(R)S
[x 325] 68 11B sESAMo(I)D
[x 144] 69 10B DefAME(R)S
[x 198] 70 13D MeDA(L)EtS
[x 220] 71 15E iDEs
[x 194] 72 15D bAbES
[x 279] 73 15D blAES
[x 355] 74 13A SoMEDeA(L)
[x 166] 75 13A SoMeDEA(L)
[x 226] 76  1E MEDuSAe
[x 350] 77  1E aMiDASE
[x 238] 78 15A MeDuSAE
[x 374] 79 15A MiSmADE
[x 401] 80  1G DAEMon(E)S
[x 266] 81  1G bEDMAt(E)S
[x 146] 82 13C DiSMA(L)Er
[x 176] 83 13B SEMibA(L)D
[x 236] 84 15A aMiDASE
[x 139] 85 15C bAsSED
[x 126] 86 11D diAM(I)DES
[x 109] 87 15C gAmMES
[x  88] 88 15A miSMADE
[x  83] 89 15C MASheD
[x 114] 90  1G MAEnaD(E)S
[x  49] 91  1F StAMpED(E)
[x  39] 92 15C bEAMeD
[x  74] 93 15C bAlMED
[x  28] 94 15C AMiDeS
[x  20] 95  1F SEADroM(E)
[x  38] 96  1F StEpDAM(E)
[x   7] 97 13F be(L)DAMES
[x   4] 98 15C AMiDES
[x  11] 99  O9 miSMADE
[x   3]100 15C AMuSED
[x   2]101 13F bE(L)DAMeS
[x   1]102  O1 MADdESt
[x   6]103 13F Do(L)MAdES
[x   2]104  O1 aMAsSED
[x  15]105  8B (PSYCHOANALYZE)d
[x   9]106  O1 SpAsMED
[x   1]107  O1 DAMSEls
[x 132]108  8B (PSYCHOANALYZE)S
[x  52]109  O1 gADSMEn
[x 117]110  O6 aAs
[x 119]111  8B (PSYCHOANALYZE)D
[x 138]112  O1 AMiDaSE
[x 198]113  O1 anADEMS
[x 162]114  O1 SeEDMAn
[x 174]115  O1 reADMES
[x 516]116  O5 aAhS
[x 488]117  O5 abAS
[x 203]118  O5 bADs
[x 488]119  O5 aDdS
[x 214]120  O5 abASE
[x 377]121  O5 adDS
[x 412]122  O5 aMaS
[x 247]123  O5 abED
[x 260]124  O5 bADS
[x 639]125  O5 aiMS
[x 352]126  O5 abASED
[x 196]127  O5 wADSEt
[x 189]128  O5 aMiD
[x 199]129  O5 blADES
[x 119]130  O5 ArEDeS
[x 207]131  O5 aMiDE
[x 147]132  O5 AMiD
[x 198]133 15H dEMAnDS
[x 159]134  O5 aMiDES
[x 119]135 15H diADEMS
[x 101]136 15H rAnDEMS
[x 264]137 15B MArDiES
[x 147]138 15H reMADES
[x 137]139 15B AMenDES
[x 144]140 15B AMaSsED
[x  76]141 15B eMbASED
[x  58]142 15B rEADMeS
[x  98]143 15B aMASsED
[x  28]144 15B aMAsSED
[x  27]145 15B StEAMeD
[x 105]146 15B chASMED
[x  40]147 15B rEMADeS
[x  67]148 15B noMADES
[x  45]149 15B SAMbaED
[x  33]150 15B vAMoSED
[x  38]151  O3 AsiDES
[x  30]152 15F SEDAriM
[x  30]153  O3 AdDiES
[x  19]154  O3 tSADEs
[x  44]155  O3 edEMAS
[x  81]156  1H SEMiD(E)Af
[x  49]157  1H SoMED(E)Al
[x  95]158  O3 ASMEar
[x  23]159  O3 aSMEAr
[x  14]160  O3 ADdErS
[x  22]161  O3 iDEAlS
[x  13]162  O3 aDAgES
[x   7]163  O4 DaMeS
[x   8]164  O3 EDeMAs
[x   4]165  O3 eDEMAs
[x   8]166  O3 ADeEMs
[x  18]167  O3 aDMASs
[x   3]168  1H DrEAM(E)rS
[x   9]169  O3 aDeEMS
[x   5]170  O3 aDEeMS
[x   3]171  O3 eDEMAS
[x   1]172  O3 ADeEMS
[x   1]173  O3 ADEeMS
[x   4]189  O5 aMAsSED
[x   8]190  O5 DiAdEMS
[x   7]191  O5 gADSMEn
[x  13]192  O5 aMASsED
[x   9]193  O5 aMiDASE
[x  22]194  O5 anADEMS
[x  15]195  O5 ApEDoMS
[x   7]196  O5 MAdDEnS
[x  12]197  O5 MiSDAtE
[x   2]198  O6 DErhAMS
[x  19]199  O6 miSMADE
[x   5]200  O6 DiSfAME
[x  16]201  O6 bEDAMnS
[x  12]202  O6 mADaMES
[x   6]203  O6 AdDeEMS
[x   4]204  O6 bEDlAMS
[x   3]205  O7 AdDEeMS
[x   6]206  O7 AdDeEMS
[x   4]207  O8 SiDEMAn
[x   3]208  O8 SeEDMAn
[x   7]210  O8 DefAMES
[x   4]211  O2 MAdDEnS
[x   3]212  O2 ADdeEMS
[x   2]213  O2 ADdEeMS
[x   1]214  O2 DESMAns
[x   2]215  O4 SMeArED
[x   1]217  O2 MADnESs
[x   4]218  O2 MiSlEAD
[x   6]219  O2 MADdEnS
[x   7]220  O2 bEDAMnS
[x   6]221  O2 maDAMES
[x   3]222  O2 bEDlAMS
[x   1]223  O2 AdDEeMS

How to interpret this notation

Here's the C++17 code I wrote

$\endgroup$
5
$\begingroup$

one word SUS = 85

This configuration has a SUS of 85:
enter image description here

Here is a chart of how many plays score X points with one example for each X:

[x1043]  1  G6 ab(A)      [x1588] 21  F5 MAZ(H)biS  [x 118] 41  F8 (H)aZMAtS  [x  17] 61  7G MaZE        [x  11] 81  I2 EMblAZ(E)S
[x3111]  2  G5 aSe(A)     [x 882] 22  G4 brAZ(A)    [x  13] 42  K4 AZyMs      [x  11] 62  7G MaZErS      [x   7] 82  7I MAmZErS
[x4106]  3  E6 ar(C)      [x 747] 23  F6 Sc(H)MAlZ  [x  21] 43  K4 aZyMS      [x   7] 63  7G MAZE        [x   1] 83  9G SiAMeZE
[x3883]  4  E6 ac(C)A     [x 471] 24  F6 MA(H)Zor   [x  16] 44  K3 aMAZEs     [x   3] 64  E5 mEZ(C)AlS   [x   1] 84  7G MEzuZAS
[x3981]  5  E6 ac(C)AS    [x 901] 25  F2 MEZuzA(H)  [x  90] 45  F2 MEzuZA(H)  [x   6] 65  7F aMaZE       [x   2] 91  7I MEzuZAS
[x2893]  6  E6 dA(C)ES    [x 162] 26  E5 Zin(C)     [x  31] 46  K3 SMAZEs     [x   5] 66  7F aMaZES      [x   4] 96  F2 MEzuZA(H)S
[x4112]  7  E6 cE(C)uM    [x 605] 27  F8 (H)aMZAhS  [x  56] 47  K3 aMAZES     [x  12] 67  7F aMAZE       [x  19] 97  K2 ecZEMAS
[x4758]  8  E5 abA(C)     [x 163] 28  E4 AZoi(C)    [x  43] 48  7H aZAn       [x   6] 68  H5 eMb(L)AZES  [x   2]102  7I ZAMouSE
[x2834]  9  E6 MA(C)ES    [x 132] 29  G4 ShAZ(A)M   [x  77] 49  7F aZAn       [x   2] 69  7F SMAZE       [x   1]105  7I ZEugMAS
[x2671] 10  E4 bASi(C)    [x 149] 30  E3 ZArnE(C)   [x  47] 50  7G beZES      [x   2] 70  H2 dAMoZE(L)S  [x   3]114  7G MEZcAlS
[x1966] 11  F3 caMAS(H)   [x  60] 31  7F sEAMS      [x  45] 51  7F SpAZ       [x   1] 71  I5 kAM(E)EZeS  [x   2]115  7G MEZAilS
[x1759] 12  E3 cASEi(C)   [x  43] 32  E2 SaZErA(C)  [x  15] 52  7G dAZErS     [x   3] 72  E5 MeZ(C)AlS   [x   1]129  K5 ZEMStvA
[x1094] 13  E6 Za(C)k     [x   6] 33  7G kAMEeZ     [x   3] 53  7G ZeAS       [x   2] 73  7I mAMZErS
[x1016] 14  E4 cuME(C)    [x  20] 34  E5 MeZ(C)Al   [x   1] 54  7I ZEugMA     [x   2] 74  7I ecZEMAS
[x 813] 15  E6 ZA(C)kS    [x  38] 35  F7 c(H)EZ     [x  15] 55  7F amAZE      [x   1] 75  9I SiAMEZe
[x 904] 16  E3 hAEMi(C)   [x 100] 36  E5 eMA(C)SEn  [x   5] 56  7F amAZES     [x   4] 76  E5 MEZ(C)AlS
[x 845] 17  F3 ZAidE(H)S  [x  43] 37  F3 geEZA(H)S  [x   8] 57  7F cEAZe      [x   4] 77  I2 SiAMEZ(E)d
[x1051] 18  E2 AMnESi(C)  [x  54] 38  E7 e(C)ZEMAS  [x   4] 58  7F cEAZeS     [x   2] 78  I2 siAMEZ(E)S
[x1683] 19  F5 sAZ(H)EnS  [x 138] 39  F3 haMZA(H)S  [x   5] 59  7F SEAZe      [x   2] 79  I2 kAMeEZ(E)S
[x 845] 20  F5 MAZ(H)bi   [x  19] 40  K3 SeAZEs     [x   2] 60  7G MaZeS      [x   4] 80  I4 siAM(E)ZES

How to interpret this notation

Most of the plays with scores near 60 are horizontal plays with the Z on 7G or 7I (double-letter score), where the Z alone contributes 40 points.

My code can search all racks for a given starting word, or all starting words for a given rack (very roughly ~1 hour), but it's too slow to do both.

$\endgroup$
2
  • $\begingroup$ What does the first column denote? E.g.[x1043]? $\endgroup$ Commented Apr 27 at 6:54
  • 1
    $\begingroup$ There are 1043 1-point plays $\endgroup$ Commented Apr 27 at 7:43

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.