01.30.07

Boggle #2: The Shortest Solver

Posted in boggle, programming at 1:40 am by danvk

Last time, we talked about how to play Boggle and the general idea of a program to find all the words on a board. This time, we’ll implement it! We’ll use Ruby, since it’s such a wonderful language.

First of all, we’ll need a dictionary of valid English words. There are plenty of different dictionaries floating around the web, and if you’re running a UNIX-style OS, you’ve already got one in /usr/share/dict/words. That dictionary is pretty bad, though. It’s designed for spellcheckers, and has no shortage of extremely questionable words (e.g. “aal” — more on this in a future post). I’ve eventually settled on the ENABLE2K list, since it seems to agree well with the scrabble dictionary and my intuition for words.

A dictionary on disk is no good, though. We need to load it into memory. Hash tables are the best built-in data structure for us, since they provide fast word lookups. Here’s the code:

Words = Hash.new
IO.foreach("words") do |line|
  line =~ /^([a-z]{3,17})\b/ and Words[$1] = true
end

There’s some slightly subtle stuff going on here. IO.foreach passes each line in a file to its block. In a display of its Perl roots, Ruby includes the trailing newline on each line. That’s what the “\b” in the regular expression is matching. In Perl, we could have written /^([a-z]{3,17})$/, since Perl interprets “$” as end-of-line. But Ruby interprets it as end-of-string, so we have to fudge. The capturing parens cut off the newline and put the word in $1, which we add to the hash.

Just a little more setting up. We’ll represent the board as a 4×4 array of strings, one for each letter on the board. Letters will come in from the command line arguments (ARGV). We also need a way to remember which words we’ve found and which cells we’ve gone through in the depth-first search.

Found = {} # = Hash.new
Prev = Array.new(4) { [false] * 4 }
Bd = Array.new(4) { [0] * 4 }
(0..15).each { |i| Bd[i/4][i%4] = ARGV[i] }

When you use multiplication on arrays in Ruby it acts like Perl’s x operator, so [0] * 4 == [0,0,0,0].

Now for the meat of the algorithm, the recursive DFS routine. When we enter a cell, we mark it as visited so that longer paths won’t illegally pass through the cell again. Then we check if we’ve formed an English word. Finally, we continue the search on paths in every direction around the cell.

Dirs = [ [-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1] ]
def solve(x, y, sofar)
  Prev[x][y]=true               # Mark our turf

  wd = sofar + Bd[x][y]
  Found[wd]=true if Words[wd]   # count the new word
  
  Dirs.each do |dx, dy|
    next unless (0..3)===(x+dx) # are we still
    next unless (0..3)===(y+dy) # on the board?
    next if Prev[x+dx][y+dy]    # have we been here before?
    solve(x+dx,y+dy,wd)         # keep going!
  end
  
  Prev[x][y] = false            # We're done here
end

When Ruby sees a single array like [1,0] passed into a block with two parameters, it automatically expands the array to match the params, which is almost always exactly what you want. The recursion bottoms out when we got trapped in a cell: Prev[x+dx][y+dy] is set on each iteration of the loop that lands on the board.

That funky === operator is the range inclusion operator. The statement (a..b)===x is entirely equivalent to a<=x && x<=b.

Finally we need to start the search from each cell and tally up the score:

(0..15).each { |i| solve(i/4, i%4, "") }

# Length: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17
Scores = [0, 0, 0, 1, 1, 2, 3, 5,11,11,11,11,11,11,11,11,11,11]
puts Found.keys.inject(0) { |sum,w| sum + Scores[w.length] }

The Enumerable.inject method is like foldr in functional languages or accumulate in the C++ STL. It takes a starting value (0 in this case) and an action on that value for each item in the enumeration.

And that, my friends, is a complete Boggle solver! How fast is this? Here's a few sample runs on my MacBook Pro:

$ time ruby short.rb a b c d e f g h i j k l m n o p
18

real    4m11.836s
user    4m8.601s
sys     0m0.777s
$ time ruby short.rb c a t d l i n e m a r o p e t s
2338

real    4m12.465s
user    4m8.631s
sys     0m0.866s

It's a strength of this algorithm that its running time is almost completely independent of the input board. But four minutes is an eternity in computer time. How much better can we do?

Here's the full source of the program:

# Load all 3-17 letter words into a hash for fast lookup
Words = Hash.new
IO.foreach("words") do |line|
  line =~ /^([a-z]{3,17})\b/ and Words[$1] = true
end

Found = Hash.new                            # hash of words we've found
Prev = Array.new(4) { [false] * 4 }         # where have we been already?
Bd = Array.new(4) { [0] * 4 }               # empty 4x4 array
(0..15).each { |i| Bd[i/4][i%4] = ARGV[i] }

# All the different directions [dx,dy] we can look from a cell
Dirs = [ [-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1] ]
def solve(x, y, sofar)
  Prev[x][y]=true               # Mark our turf

  wd = sofar + Bd[x][y]
  Found[wd]=true if Words[wd]   # count the new word
  
  Dirs.each do |dx,dy|
    next unless (0..3)===(x+dx) # are we still
    next unless (0..3)===(y+dy) # on the board?
    next if Prev[x+dx][y+dy]    # have we been here before?
    solve(x+dx,y+dy,wd)         # keep going!
  end
  
  Prev[x][y] = false            # We're done here
end

# Start a depth-first search from each cell on the board
(0..15).each { |i| solve(i/4, i%4, "") }

#         0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17
Scores = [0, 0, 0, 1, 1, 2, 3, 5,11,11,11,11,11,11,11,11,11,11]
puts Found.keys.inject(0) { |sum,w| sum + Scores[w.length] }

In the spirit of code golf, I tried to make this program as short as I possibly could. Here's the result: a 12 line, slow-as-hell Boggle solver that I won't dignify with an explanation. Someone claimed he could write a shorter one in Haskell. I'll believe it when I see it!

W, F = {}, {}
IO.foreach("words") { |l| l =~ /^([a-z]{3,17})\b/ and W[$1] = 1 }
B = Array.new(6) { [""]*6 }
(0..15).each { |i| B[1+i/4][1+i%4] = ARGV[i] }
def s(x, y, w)
  p, B[x][y] = B[x][y], ""
  F[w+p]=true if W[w+p]
  (0..8).map{|i|[i/3-1,i%3-1]}.each {|e,f| s(x+e,y+f,w+p) if B[x+e][y+f]!=""}
  B[x][y] = p
end
(0..15).each { |i| s(1+i/4, 1+i%4, "") }
puts F.keys.inject(0){|s,w| s+(w.size<8 ? [0,0,0,1,1,2,3,5][w.size] : 11)}

Permalink