December 28: Finding paths on a grid in Ruby with recursion

8 min readDec 29, 2020

Neither COVID nor a weeklong winter break will stop me from coding, no-sir-ee! This week’s blog post even includes code you can fork and clone for yourself! I’m covering today’s subject, grid path problems, because I’ve seen a few solutions on search engines but never one in Ruby. Let’s dive in!

Background: What’s a grid path problem? Why should we care?

Grid path problems are widely studied in applied mathematics, and software engineers are commonly asked to solve them in job interviews. That’s because they require breaking a complicated problem down into smaller parts, demonstrating a programmer’s computational thinking skills.

There are dozens of variations of the grid path problem (also called the grid traversal or matrix path problem), all more or less the same in their essence and core. Imagine a little grid, like a miniature version of an ordinary chess board, with the King in the top-left corner. How do we find the chess King’s shortest path to the bottom right corner?

Chess board of ebony inlaid with ivory from the Mughal Empire, 16th century (Photo credit: Metropolitan Museum of Art)

Solutions to the grid path problem have numerous profound real-world applications. The most obvious are games played on grids, like chess, checkers, Conquest, Quoridor, or non-western games like Go, Shogi or Chaturanga. But, the grid path problem is also a good proxy for many other non-game domains that can be modeled as matrices with nodes. Navigation apps like Waze, Mapquest and Google Maps model addresses, intersections and freeway exits as nodes on a massive matrix of streets and highways. (Navigation software does not employ the pure naïve recursion I make use of here. Those apps replace a great deal of the recursion that would otherwise be necessary with very sophisticated heuristics, cooked up by very well-paid nerds, for performance reasons that will become clear below. But, the core principle they operate on is essentially the same.)

What a human would do

If I were to ask you, dear reader, to find the path a chess King could take between two given squares, you would probably follow a checklist similar to the one below:

Look at all the current square’s adjacent squares;
Find all the squares adjacent to each of the current square’s adjacent squares;
Repeat (i.e., keep finding adjacent squares), excluding squares already in the path, until you’ve arrived at the target destination square.

This is exactly the strategy our code will use to solve the grid path problem. Let’s write it!

Finding adjacent squares

In the context of this Ruby method, a grid will be represented as an array of row arrays (a two-dimensional or nested array) like so:

[ [ "00", "01", "02", "03" ],
  [ "10", "31", "12", "13" ],
  [ "20", "21", "22", "23" ],
  [ "30", "33", "32", "33" ] ]

Each square can be identified by an array of size 2 in the format [ row, column ], so for the above array [ 2, 3 ] would represent square "23".

Now examine the following method, which takes as arguments a board and the coordinates of a square, and returns an array of coordinates of adjacent_squares:

def adjacent_squares( board, coordinates )
   rows = [ coordinates[ 0 ] - 1, coordinates[ 0 ], coordinates[ 0 ] + 1 ]
   columns = [ coordinates[ 1 ] - 1, coordinates[ 1 ], coordinates[ 1 ] + 1 ]
   all_adjacent_squares = rows.product( columns )
   all_adjacent_squares.select{ | square | square[ 0 ].between?( 0, board.size - 1) && square[ 1 ].between?( 0, board.first.size - 1 ) && square != coordinates }
end

First, we define two arrays (rows and columns), containing the rows above and below and the columns to the left and right, respectively, as well as the current row/column, of the coordinates argument. Then, we use Ruby’s Array.product( Array ) method, to produce every possible combination of coordinates from rows and columns:

[ 0, 1, 2 ].product( [ 1, 2, 3 ] )
   # => [[0, 1], [0, 2], [0, 3], [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3]]

Finally, we need to remove the current square’s coordinates from our list of all_adjacent_squares— we don’t want to be running around in circles! We also need to account for squares which are on the edge of the grid; if we don’t, we’ll get nil values and/or some very wacky incorrect coordinates (since Array[ -1 ] in Ruby means the last element of an array). We can remove the current square while handling our edge cases with one long .select enumerable — it isn’t pretty, but it gets the job done!

Note that in our .select enumerable, we access the height and width of our board with board.size and board.first.size respectively. This way, our method will still work on grids of any dimension, even non-square grids or grids with only one row/column.

Note as well that this method produces orthogonally- and diagonally-adjacent squares. If we want only orthogonally-adjacent (up/down/left/right) squares, without diagonals, we’ll have to make some slight adjustments to our method, like below:

def orthogonally_adjacent_squares( board, coordinates )
   row = coordinates[ 0 ]
   column = coordinates[ 1 ]
   all_adjacent_squares = [ [ row - 1, column ], [ row, column + 1 ], [ row + 1, column ], [ row, column - 1 ] ]
   all_adjacent_squares.select{ | square | square[ 0 ].between?( 0, board.size - 1) && square[ 1 ].between?( 0, board.first.size - 1 ) }
end

Here in orthogonally_adjacent_squares, we won’t have to remove the current square’s coordinates in the last line because it’s easiest to just hard-code our array of all_adjacent_squares without it.

Finding all possible paths between two squares with recursion

A *matryoshka doll is an example of aesthetic recursion: Each doll contains smaller versions of itself (Photo credit: Wikimedia Foundation)*

Now that we have a working method to give us adjacent_squares on aboard given a square’s coordinates, we can build a method to produce all_possible_paths. To do this, we’ll write a recursive method — a method that calls itself!

Recursion is absolutely central to computer science and software engineering because it has so many potential applications. It’s so powerful, in fact, that programming languages exist which only use recursion and have no loops or other flow controls!

The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.
— Niklaus Wirth

A deep dive into recursion is far, far beyond the scope of this blog — to be honest, it’s far beyond the scope of most careers. All I ask, in the context of traversing grids, is that you remember two things…

Recursion solves a big problem (the recursive case) by repeatedly solving an identical but smaller problem (the base case). The base case looks the same as the recursive case — just on a smaller scale.
When using recursion, one must always specify a base case and make sure your program reaches it. Without reaching a base case, a recursive method will repeat indefinitely, and Ruby will quickly give up and die, gurgling out a SystemStackError in defeat.

So, with all this in mind, think back to our checklist for humans above: find squares adjacent to the current square, then keep finding adjacent squares not already in the current path until we reach our destination. Sounds familiar, doesn’t it? It’s logical to conclude that:

Our recursive case is finding the next set of adjacent squares, and;
Our base case is either reaching our destination or reaching a duplicate square.

Now consider the method below, which recursively adds possible_paths to a path_list. It accepts the following arguments:

a board
a set of current_coordinates
the coordinates of a destination
an array to keep track of the path_so_far
an array of finished paths called path_list

def possible_paths( board, current_coordinates, destination, path_so_far, path_list )
   current_square_value = board[ current_coordinates[ 0 ] ][ current_coordinates[ 1 ] ]
   if current_coordinates == destination
      path_so_far.push( current_square_value )
      path_list << path_so_far
   else
      adjacent_squares( board, current_coordinates ).each do | adjacent_coordinate |
         if !path_so_far.include?( current_square_value )
            next_possible_path = path_so_far.clone.push( current_square_value )
            possible_paths( board, adjacent_coordinate, destination, next_possible_path, path_list )
         end
      end
   end
end

What’s going on here? Let’s examine this method step by step:

First, we define current_square_value by getting the value in the current_coordinates of our board;
Next we start an if statement by checking so see if we’ve arrived at our first base case — i.e., when our current_coordinates are the same as our destination‘s coordinates. If we’ve arrived at our destination, hooray! We dance a jig, .push the current_square_value onto the path_so_far, add the path_so_far to our path_list, and stop recurring;
If we haven’t arrived at our destination yet, we start enumerating over .each adjacent_coordinate in adjacent_squares. We can stop recurring if a particular adjacent_coordinate leads to a square we’ve already visited (our second base case), so we check for that in .each adjacent_coordinate by asking if !path_so_far.include?( current_square_value ). That way, if our adjacent_coordinate has already been counted in path_so_far, we stop recurring by skipping the recursion block and thus avoid giving Ruby an aneurysm;
Finally, if we haven’t arrived at either base case yet, we need to keep recurring! So, inside our .each enumerable checking each of our adjacent_squares, we create a new variable called next_possible_path, assign to next_possible_path a .clone of the current path with the current_square_value .pushed onto it, and then recur by calling possible_paths again — this time with our next_possible_path.

Whew! That may seem like pretty heavy lifting, but think of how much work recursion is doing for us. When starting at a corner ([ 0, 0 ]) and ending at the opposite corner ([ board.size, board.first.size ]), this method generates 96,371 unique paths on a four-by-four matrix and 494,596 paths on a three-by-six matrix—all in just a dozen lines of code. That’s the power of recursion!

Conclusion: The limitations of recursion

Now that we have a method to generate unique possible_paths, finding the shortest is a piece of cake. All we have to do is create a path_list array, populate it with paths using the possible_paths method we just wrote, sort it by .size, and return the .first (the shortest):

def shortest_path( board, start_coordinates, end_coordinates )
   path_list = []
   possible_paths( board, start_coordinates, end_coordinates, [], path_list)
   path_list.sort_by( &:size ).first
end

It’s also very easy to re-factor the above methods to solve other grid path problems. We can, for example, change our base case in possible_paths so that we only find paths of a certain .length. Or imagine that some of the squares on our chess board are hot lava and thus impassable — we can change our adjacent_squares method to make certain squares off-limits.

We’ve seen that recursion is incredibly powerful, but that power creates one huge drawback: recursion can create very big instances. Exponentially big, as a matter of fact. See for yourself: recursion in Ruby is manageably quick when traversing matrices with about 20 nodes or so, but for larger grids, grab a snack and get comfortable because you’ll be waiting a good long while. Ruby is especially vulnerable to this because of how it manages its stack, and because its function calls are relatively slow. The difference is less noticeable in languages like Lisp or C, but even then your computer will slow to a crawl and get sizzling hot because it’ll be sucking up more battery power than a Sega Nomad.

In conclusion: recursion is incredibly useful, but consider your base case and the size of the data you’re iterating over. Balance your needs and the scale of the problem you’re solving with the limitations of your language and your hardware. When unleashing the power of recursion, remember the wise words of Ruby Spiderman: great_power.eq?( great_responsibility )!