So, I did what any decent, but downtrodden word game player who happens to have coding skills would do. (You might say I wrote lots of programs as a kid). I wrote a program to replace my poorly-skilled self. I had a boring plane ride by myself last week. I brought my netbook along and whipped up a little Python script to solve any given Scramble board.
Since the two inputs, the board configuration and the dictionary, are a fixed size and not too big, I can get away with a less than efficient approach to finding all the solutions. I just put all the possible words in a set, subtract some words, and use the string.startswith method to prune the game tree. After subtracting proper nouns, words that are too long or too short, or that are not comprised of letters on the board, the dictionary only has a few thousand possible words, given a typical board setup. If there were more possible words, for efficiency I might have needed to use a trie instead of a set to store the word list. If the game had an even larger problem space, for instance if the game had a 5x5 or larger grid, I probably would have needed to settle for a heuristic to focus on areas of the board likely to produce high scoring words. As it is, though, it takes more time to key in the board set up than it does to run the solver to brute-force a complete set of solutions, on my little eeepc.
The code is here. It's a pretty straightforward solution. However, if any beginners out there want a code walk, let me know in the comments. It could be a good introduction to recursion. The program should run on any system. But, I rely on the *nix system commands sort, head, and more to present the output in a way that makes it easy to key-in. I suppose this presentation approach could be rolled into the script code itself.
Given this board:
# Set up the board. Use single letters or QU for Qu. grid = (('QU', 'E', 'W', 'M'), ('A', 'L', 'O', 'E'), ('A', 'A', 'D', 'O'), ('R', 'E', 'T', 'S')) # Set up double and triple letters. lmult = ((1,2,1,1), (1,2,1,1), (1,1,1,1), (1,1,1,1)) # Set up double and triple word bonuses. wmult = ((1,1,1,1), (1,1,1,1), (1,1,2,1), (1,1,1,1))This command supplies me with the 65 best solutions, one at a time, in a convenient order:
scramble_solver$ python scram.py | sort -rn -k2 | head -65 | sort | more -1 Focusing on 2774 word dictionary. ALATED 26 |....|AL..|.AD.|.ET. ALDER 21 |....|AL..|..D.|RE.. DALE 18 |.E..|.L..|.AD.|.... DEMO 16 |...M|..OE|..D.|.... DERATS 20 |....|....|.AD.|RETS --More--
I hope you're not too mad, JV. And congratulations. :)