Boggle board solver in Ruby The following is my attempt at creating a Boggle board solver in Ruby. It's not especially fast. I would love to have input on how the solution can either be sped up, or whether a different algorithm might be applied that is faster.

The solution corresponds to my answer on a related question on the Math Stack Exchange site: https://math.stackexchange.com/a/2908479/30919

require 'set'
# List of words in a file, imported into sorted set for quick lookup:
WORDS = SortedSet.new(open('wordlist.txt').readlines.map(&amp;:chomp))
# Possible directions from a space and their x/y deltas:
DIRS = { n: [0, -1], ne: [1, -1], e: [1, 0], se: [1, 1], s: [0, 1], sw: [-1, 1], w: [-1, 0], nw: [-1, -1] }.freeze

# Note on "Qu" -- "Qu" should require special handling in the

# Sample board we want to solve; we could create a random board with
# the known configuration of the cubes. 
# For 'Qu' on the Boggle board, only 'Q' is entered in @board, because the traversion routine
# has special handling for 'Q' by adding a 'U' each time
@board = [
  %w[ N P E R ],
  %w[ P L R O ],
  %w[ I U N T ],
  %w[ J E G V ]  
]

# This method determines the next position based on the currend position
# and direction. If the position is out of bounds, it returns nil
def next_pos(position, direction)
  npos = [
    position[0] + DIRS[direction][0],
    position[1] + DIRS[direction][1]
  ]
  return nil if (npos[0] &lt; 0) || (npos[1] &lt; 0) ||
                (npos[0] &gt; 3) || (npos[1] &gt; 3)
  npos
end

@stack = [] # Stack containing the positions traversed
# NB: **The letters have their own stack due to the special handling of "Qu"**
@letters = [] # Corresponding letters from the positions in stack
@found_words = SortedSet.new # Words found 
def traverse(cpos)

    # Nested method that handles popping of stack with special 'Qu' handling (because it's used more than once)
    def pop_stack
        @stack.pop
        @letters.pop
        # Special handling for "Qu":
        @letters.pop if @letters.last == "Q"        
    end

  #The longest words in my list are 15 letters - omit this check if you have more
  return if @stack.length == 15 

  # Push current position and letters collected so far on the respective stacks
  @stack &lt;&lt; cpos
  @letters &lt;&lt; @board[cpos[0]][cpos[1]]
  # Special handling for Qu:
  @letters &lt;&lt; "U" if @letters.last == "Q"

  # From 2 letters onwards, check whether this path is worth pursuing
  if @stack.length &gt;= 2
    unless WORDS.grep(/^#{@letters.join}/).any?
      pop_stack
      return
    end
  end

  # From 3 letters onwards, check if the word is in the dictionary
  if @stack.length &gt;= 3
    word = @letters.join
    if WORDS.include?(word)
      @found_words &lt;&lt; word
    end
  end

  # Try each direction in succession from the current position
  DIRS.keys.each do |dir|
    npos = next_pos(cpos, dir) # Calculate next pos from current pos
    next unless npos # Check it is not out of bounds
    # Check whether the new position had been visited in current stack
    visited = false
    @stack.reverse_each do |pos|
      if pos == npos
        visited = true
        break 
      end
    end
    next if visited # Skip the new position if it had been visited
    traverse(npos) # Start looking from next position
  end

  # Take the last position/letter off the stack before returning
  pop_stack

end

# Traverse from every square on the board
4.times.map do |x|
  4.times.map do |y|
    traverse([x, y])
  end
end

puts @found_words.sort
I can't comment on Ruby style, but there are a couple of algorithmic points which don't need Ruby knowledge to identify.




  if @stack.length &gt;= 2
    unless WORDS.grep(/^#{@letters.join}/).any?
      pop_stack
      return
    end
  end



Although you've preprocessed the wordlist into a sorted data structure with logarithmic time lookup, grep seems to be a method from Enumerable and I can't see any indication that there are special cases. In other words, this is (worst case) doing a linear scan of the entire wordlist. There should be a massive speed improvement either by exploiting the SortedSet interface or (more likely) by preprocessing the wordlist into a trie. The latter gives the advantage that you can pass the current node down the stack and not have to run the entire route from the root every time.




    # Check whether the new position had been visited in current stack
    visited = false
    @stack.reverse_each do |pos|
      if pos == npos
        visited = true
        break 
      end
    end



Again, this is doing a linear scan for something which doesn't need to be so slow. The OO way would be to use a Set, which ought to have fast member? checks. The optimisation-over-all approach would be to use an integer as a bitmask. Either approach requires minimal maintenance on the stack.