kleemans.ch

I digged out a script which I wrote some months ago, for finding the best words in Boggle / Scramble / Ruzzle etc. With ca. 210k words in a dictionary, each word is checked if it can be represented on the board. From all possible words, their values are calculated and then printed in descending order.

Sample grid:

My script:

Any multipliers (double/triple word/letter) are not taken into account. But at least you should manage to get the "the ultimate move" achievement in Ruzzle.

Code

The code basically uses a simple search algorithm, exploring the possible neighbor letters and checking if they're in the dictionary.

All resulting entries are then scored based on letter value, and the entries are sorted top down, to give the most valuable ones first.

for word in words:
    # speed & correctness
    if len(word) < 2:
        continue

    possible = True
    promising = True
    starting_field = '0'
    hist = starting_field

    for letter in word:
        if letter not in grid:
            possible = False

    while possible:     
        l = len(hist)
        last_number = '0'
        if l > 1:
            last_number = int(hist[l-2:l-1], 16)
        this_number = int(hist[l-1:], 16)

        if grid[this_number] == word[l-1] and promising: # letter is correct & promising
            if l == len(word): # if last letter ist correct, word is valid
                log("> Letter is valid, word found!")
                matches.append(word)
                possible = False
            else: # checking if adding new number is valid
                log("> Letter correct, adding number")
                this_index = len(graph[rd[this_number]])
                letter_added = False
                for i in range(0, this_index):
                    new_number = str(graph[rd[this_number]][i])
                    log("new number: "+new_number)
                    if new_number not in hist: # if field not in use
                        hist += new_number
                        letter_added = True
                        break
                if not letter_added:
                    possible = False # dead end
        else: # letter not correct
            promising = True
            log("> Letter not correct or not promising")
            if len(hist) == 1: # change starting field
                start = int(hist, 16)
                if start == 15: # last possibility reached
                    log("> F reached with no possibilities")
                    possible = False
                else:
                    hist = rd[int(hist, 16) + 1] # increment starting field
            else: # not starting field
                # get index
                line = graph[rd[last_number]]
                log("> calculating index in "+str(line))
                index = "lulz"
                for j in range(0, len(line)):
                    if line[j] == rd[this_number]:
                        index = j
                        log("> index found: " + str(j))

                last_index = len(graph[rd[last_number]])
                incremented = False
                log("> looping from "+ str(index) + " to " + str(last_index))
                for i in range(index, last_index):
                    log("> possibilities: " + str(graph[rd[last_number]]))
                    new_number = graph[rd[last_number]][i]
                    log("> checking " + new_number + " = " + grid[int(new_number, 16)] + " for adding...")
                    if new_number not in hist: # only if field not already in use
                        log("> adding " + new_number)
                        hist = hist[:len(hist)-1] + new_number
                        incremented = True
                        break
                if not incremented: # else go back one step
                    log("> not incremented, go back one step")
                    if last[:len(word)-1] == hist: # check if last possibility
                        log("> breaking, last possibility: " + hist)
                        possible = False
                    else:
                        hist = hist[:l-1]
                        promising = False

# calculate most valuable matches
matches_count = len(matches)
l = dict(zip(matches, [val(n) for n in matches]))

# get a sorted instance of dict (list of tuples)
l = sorted(l.iteritems(), key = operator.itemgetter(1), reverse=True)

# Output
print "\n", matches_count, "results found: "

for i in l:
    print i[0], "-", i[1], "points"

You can find the whole source code (including an English dictionary, which is necessary) scramble-best-words.