Graph Algorithms in Board Games!
For last week’s problem we started learning about graph algorithms, focusing on depth-first-search. Today we’ll do a problem from an old board game that will require us to use breadth-first-search. We’ll also learn about a special library in Haskell that lets us solve these types of problems without needing to implement all the details of these algorithms.
To learn more about this library and graph algorithms in Haskell, you should check out our problem solving course, Solve.hs! Module 3 of the course focuses on algorithms, with a special emphasis on graph algorithms!
The Problem
Today’s problem comes from a kids board game called Snakes and Ladders, which will take a little bit to explain. First, we imagine we have a square board in an N x N grid, where each cell is numbered 1 to N^2. The bottom left corner is always “1”, and numbers increase in a snake-like fashion. First the increase from left to right along the bottom row. Then they go from right to left in the next row, before reversing again. Here’s what the numbers look like for a 6x6 board:
36 35 34 33 32 31
25 26 27 28 29 30
24 23 22 21 20 19
13 14 15 16 17 18
12 11 10 9 8 7
1 2 3 4 5 6The “goal” is to reach the highest numbered tile, which is either in the top left (for even grid sizes) or the top right (for odd grid sizes). One moves by rolling a 6-sided die. Given the number on the die, you are entitled to move that many spaces. The ordinary path of movement is following the increasing numbers.
As is, the game is a little boring. You just always want to roll the highest number you can. However, various cells on the grid are equipped with “snakes” or “ladders”, which can move you around the grid if your die roll would cause your turn to end where these items start. Ladders typically move you closer to the goal, snakes typically move you away from the goal. Here’s an illustrative picture of a board:
We can represent such a board by putting an integer on each cell. The integer -1 represents an ordinary cell, where you would simply proceed to the next cell in order. However, we can represent the start of each snake and ladder with a number corresponding to the cell number where you end up if your die role lands you there. Here’s an example:
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 35 -1 -1 13 -1
-1 -1 -1 -1 -1 -1
-1 15 -1 -1 -1 -1This grid has two ladders. The first can take you from position 2 to position 15 (see the bottom left corner). The second can take you from position 14 to position 35. There is also a snake, that will take you back from position 17 to position 13. Note that no matter the layout, you can only follow one snake or ladder on a turn. If you end your turn at the beginning of a ladder, which takes you to the beginning of another ladder, you do not take the second ladder on that turn.
Our objective is to find the smallest number of dice rolls possible to reach the goal cell (which will always have -1). In this case, the answer is 4. Various combinations of 3 rolls can land us on 14, which will take us to 35. Then rolling 1 would take us to the goal.
It is possible to contrive a board where it is impossible to reach the goal! We need to handle these cases. In these situations we must return -1. Here is such a grid, with many snakes, all leading back to the start!
1 1 -1
1 1 1
-1 1 1The Algorithm
This is a graph search problem where each step we take carries the same weight (one turn), and we are trying to find the shortest path. This makes it a canonical example of a Breadth First Search problem (BFS).
We solve BFS by maintaining a queue of search states. In our case, the search state might consist simply of our location, though we may also want to track the number of steps we needed to reach that location as part of the state.
We’ll have a single primary loop, where we remove the first element in our queue. We’ll find all its “neighbors” (the states reachable from that node), and place these on the end of the queue. Then we’ll continue processing.
BFS works out so that states with a lower “cost” (i.e. number of turns) will all be processed before any states with higher cost. This means that the first time we dequeue a goal state from our queue, we can be sure we have found the shortest path to that goal state.
As with last week’s problem, we’ll spend a fair amount of effort on our “neighbors” function, which is often the core of a graph solution. Once we have that in place, the mechanics of the graph search generally become quite easy.
Rust Solution
Once again we’ll start with Rust, because we’ll use a special trick in Haskell. As stated, we want to start with our neighbors function. We’ll represent a single location just using the integer representing it on the board, not its grid coordinates. So at root, we’re taking one usize and returning a vector of usize values. But we’ll also take the board (a 2D vector of integers) so we can follow the snakes and ladders. Finally, we’ll pass the size of the board (just N, since our board is always square) and the “goal” location so that we don’t have to recalculate these every time:
pub fn neighbors(n: usize, goal: usize, board: &Vec<Vec<i32>>, loc: usize) -> Vec<usize> {
let mut results = Vec::new();
...
return results;
}The basic idea of this function is that we’ll loop through the possible die rolls (1 to 6) and return the resulting location from each roll. If we find that the roll would take us past the goal, then we can safely break:
pub fn neighbors(n: usize, goal: usize, board: &Vec<Vec<i32>>, loc: usize) -> Vec<usize> {
let mut results = Vec::new();
for i in 1..=6 {
if loc + i > goal {
break;
}
...
}
return results;
}How do we actually get the resulting location? We need to use the board, but in order to use the board, we have to convert the location into 2D coordinates. So let’s just write the frame for a function converting a location into coordinates. We’ll fill it in later:
pub fn convert(n: usize, loc: usize) -> (usize, usize) {
...
}Assuming we have this function, the rest of our neighbors logic is easy. We check the corresponding value for the location in board. If it is -1, we just use our prior location added to the die roll. Otherwise, we use the location given in the cell:
pub fn neighbors(n: usize, goal: usize, board: &Vec<Vec<i32>>, loc: usize) -> Vec<usize> {
let mut results = Vec::new();
for i in 1..=6 {
if loc + i > goal {
break;
}
let (row, col) = convert(n, loc + i);
let next = board[row][col];
if next == -1 {
results.push(loc + i);
} else {
results.push(next as usize);
}
}
return results;
}So let’s fill in this conversion function. It’s tricky because of the snaking order of the board and because we start from the bottom (highest row index) and not the top. Nonetheless, we want to start by getting the quotient and remainder of our location with the side-length. (We subtract 1 since our locations are 1-indexed).
pub fn convert(n: usize, loc: usize) -> (usize, usize) {
let rowBase = (loc - 1) / n;
let colBase = (loc - 1) % n;
...
}To get the final row, we simply take n - rowBase - 1. The column is trickier. We need to consider if the row base is even or odd. If it is even, the row is going from left to right. Otherwise, it goes from right to left. In the first case, the modulo for the column gives us the right column. In the second case, we need to subtract from n like we did with rows.
pub fn convert(n: usize, loc: usize) -> (usize, usize) {
let rowBase = (loc - 1) / n;
let colBase = (loc - 1) % n;
let row = n - rowBase - 1;
let col =
if rowBase % 2 == 0 {
colBase
} else {
n - colBase - 1
};
return (row, col);
}But that’s all we need for conversion!
Now that our neighbors function is closed up, we can finally write the core solution. For the Rust solution, we’ll define our “search state” as including the location and the number of steps we took to reach it, so a tuple (usize, usize). We’ll create a VecDeque of these, which is Rust’s structure for a queue, and insert our initial state (location 1, count 0):
use std::collections::VecDeque;
pub fn snakes_and_ladders(board: Vec<Vec<i32>>) -> i32 {
let n = board.len();
let goal = board.len() * board[0].len();
let mut queue: VecDeque<(usize, usize)> = VecDeque::new();
queue.push_back((1,0));
...
}We also want to track the locations we’ve already visited. This will be a hash set of the locations but not the counts. This is necessary to prevent infinite loops. Once we’ve visited a location there is no advantage to considering it again on a later branch (with this problem at least). We’ll also follow the practice of considering a cell “visited” once it is enqueued.
use std::collections::VecDeque;
use std::collections::HashSet;
pub fn snakes_and_ladders(board: Vec<Vec<i32>>) -> i32 {
let n = board.len();
let goal = board.len() * board[0].len();
let mut queue: VecDeque<(usize, usize)> = VecDeque::new();
queue.push_back((1,0));
let mut visited = HashSet::new();
visited.insert(1);
...
}Now we’ll run a loop popping the front of the queue and finding the “neighboring” locations. If our queue is empty, this indicates no path was possible, so we return -1.
use std::collections::VecDeque;
use std::collections::HashSet;
pub fn snakes_and_ladders(board: Vec<Vec<i32>>) -> i32 {
let n = board.len();
let goal = board.len() * board[0].len();
let mut queue: VecDeque<(usize, usize)> = VecDeque::new();
queue.push_back((1,0));
let mut visited = HashSet::new();
visited.insert(1);
while let Some((idx, count)) = queue.pop_front() {
let ns = neighbors(n, goal, &board, idx);
...
}
return -1;
}Now processing each neighbor is simple. First, if the neighbor is the goal, we’re done! Just return the dequeued count plus 1. Otherwise, check if we’ve visited the neighbor before. If not, push it to the back of the queue, along with an increased count:
pub fn snakes_and_ladders(board: Vec<Vec<i32>>) -> i32 {
let mut queue: VecDeque<(usize, usize)> = VecDeque::new();
queue.push_back((1,0));
let n = board.len();
let goal = board.len() * board[0].len();
let mut visited = HashSet::new();
visited.insert(1);
while let Some((idx, count)) = queue.pop_front() {
let ns = neighbors(n, goal, &board, idx);
for next in ns {
if next == goal {
return (count + 1) as i32;
}
if !visited.contains(&next) {
queue.push_back((next, count + 1));
visited.insert(next);
}
}
}
return -1;
}This completes our BFS solution! Here is the complete code:
use std::collections::VecDeque;
use std::collections::HashSet;
pub fn convert(n: usize, loc: usize) -> (usize, usize) {
let rowBase = (loc - 1) / n;
let colBase = (loc - 1) % n;
let row = n - rowBase - 1;
let col =
if rowBase % 2 == 0 {
colBase
} else {
n - colBase - 1
};
return (row, col);
}
pub fn neighbors(n: usize, goal: usize, board: &Vec<Vec<i32>>, loc: usize) -> Vec<usize> {
let mut results = Vec::new();
for i in 1..=6 {
if loc + i > goal {
break;
}
let (row, col) = convert(n, loc + i);
let next = board[row][col];
if next == -1 {
results.push(loc + i);
} else {
results.push(next as usize);
}
}
return results;
}
pub fn snakes_and_ladders(board: Vec<Vec<i32>>) -> i32 {
let mut queue: VecDeque<(usize, usize)> = VecDeque::new();
queue.push_back((1,0));
let n = board.len();
let goal = board.len() * board[0].len();
let mut visited = HashSet::new();
visited.insert(1);
while let Some((idx, count)) = queue.pop_front() {
let ns = neighbors(n, goal, &board, idx);
for next in ns {
if next == goal {
return (count + 1) as i32;
}
if !visited.contains(&next) {
queue.push_back((next, count + 1));
visited.insert(next);
}
}
}
return -1;
}Haskell Solution
For our Haskell solution, we’re going to use a special shortcut. We’ll make use of the Algorithm.Search library to handle the mechanics of the BFS for us. The function we’ll use has this type signature (slightly simplified):
bfs :: (state -> [state]) -> (state -> Bool) -> state -> Maybe [state]We provide 3 inputs. First is the “neighbors” function, taking one state and returning its neighbors. Second is the “goal” function, telling us if a state is our final goal state. Finally we give it the initial state. If a goal is reachable, we receive a path to that goal. If not, we receive Nothing. Since this library provides the full path for us automatically, we won’t track the number of steps in our state. Our “state” will simply be the location. So let’s begin by framing out our function:
snakesAndLadders :: A.Array (Int, Int) Int -> Int
snakesAndLadders board = ...
where
((minRow, minCol), (maxRow, _)) = A.bounds board
n = maxRow - minRow + 1
goal = n * n
convert :: Int -> (Int, Int)
neighbor :: Int -> Int
neighbors :: Int -> [Int]Let’s start with convert. This follows the same rules we used in our Rust solution, so there’s not much to say here. We just have to make sure we account for non-zero start indices in Haskell arrays by adding minRow and minCol.
snakesAndLadders :: A.Array (Int, Int) Int -> Int
snakesAndLadders board = ...
where
((minRow, minCol), (maxRow, _)) = A.bounds board
n = maxRow - minRow + 1
goal = n * n
convert :: Int -> (Int, Int)
convert loc =
let (rowBase, colBase) = (loc - 1) `quotRem` n
row = minRow + (n - rowBase - 1)
col = minCol + if even rowBase then colBase else n - colBase - 1
in (row, col)Now we’ll write a neighbor helper that converts a single location. This just makes our neighbors function a lot cleaner. We use the same logic of checking for -1 in the board, or else using the value we find there.
snakesAndLadders :: A.Array (Int, Int) Int -> Int
snakesAndLadders board = ...
where
((minRow, minCol), (maxRow, _)) = A.bounds board
n = maxRow - minRow + 1
goal = n * n
convert = ...
neighbor :: Int -> Int
neighbor loc =
let coord = convert loc
onBoard = board A.! coord
in if onBoard == -1 then loc else onBoardNow we can write neighbors with a simple list comprehension. We look through each roll of 1-6, add it to the current location, filter if this location is past the goal, and then calculate the neighbor.
snakesAndLadders :: A.Array (Int, Int) Int -> Int
snakesAndLadders board = ...
where
((minRow, minCol), (maxRow, _)) = A.bounds board
n = maxRow - minRow + 1
goal = n * n
convert = ...
neighbor = ...
neighbors :: Int -> [Int]
neighbors loc =
[neighbor (loc + i) | i <- [1..6], loc + i <= goal]Now for the coup-de-grace. We call bfs with our neighbors function. The “goal” function is just (== goal), and the starting state is just 1. It will return our shortest path, and so we just return its length:
snakesAndLadders :: A.Array (Int, Int) Int -> Int
snakesAndLadders board = case bfs neighbors (== goal) 1 of
Nothing -> (-1)
Just path -> length path
where
((minRow, minCol), (maxRow, _)) = A.bounds board
n = maxRow - minRow + 1
goal = n * n
convert :: Int -> (Int, Int)
convert loc =
let (rowBase, colBase) = (loc - 1) `quotRem` n
row = minRow + (n - rowBase - 1)
col = minCol + if even rowBase then colBase else n - colBase - 1
in (row, col)
neighbor :: Int -> Int
neighbor loc =
let coord = convert loc
onBoard = board A.! coord
in if onBoard == -1 then loc else onBoard
neighbors :: Int -> [Int]
neighbors loc =
[neighbor (loc + i) | i <- [1..6], loc + i <= goal]And that’s our complete Haskell solution!
Conclusion
If you take our Solve.hs course, Module 3 is your go-to for learning about graph algorithms! You’ll implement BFS from scratch in Haskell, and learn how to apply other helpers from Algorithm.Search. In next week’s article, we’ll do one more graph problem that goes beyond the basic ideas of DFS and BFS.