Graphs and Boards
Graphs and Boards
Algorithmically Speaking - #6: Exploring how to model board games as graph problems.
Hello there!
After three weeks of learning the basics of graphs, I think it is time to show you examples of how we can translate real-life problems to the graph theory domain.
This will be the last of a series of posts introducing the basic concepts of graph theory before we dive into topics such as traversals, and finding cycles, among others.
Here’s a summary of what we have covered in the previous editions:
Introduction to the concepts of nodes, edges, and connectivity.
Defining what are neighbors, degrees, and colorings in graphs.
How to represent graphs in a computer program.
Today, we will learn about practical examples of how to use graphs in real life. For that, we are going to see examples of “games” that are played on boards. They might seem unrelated to graphs, but the truth is that they are more closely related than you might think.
At the end of the post, you will find some algorithmic challenges so you can try and apply some of the topics that I will explain today. Feel free to skip to that part if you think you already have the necessary skills to solve them.
Let’s begin!
An Initial Problem
Let’s dive in straight to the matter. Take a look at the following problem and think about how you would approach it:
By simple inspection, we can notice that there are three “sets“ of floor tiles that can be identified as “rooms“. These are all the rooms highlighted and numbered:
Intuitively, we identify these “connected“ regions and we sort them out as “rooms” because it just makes sense in our heads.
But what if this was the input to a program? How could we design an algorithm that a computer will execute to find the number of “rooms” in any map of a house that uses this representation?
Well, unfortunately, before thinking about designing algorithms we have to think about modeling this problem in terms that a computer can understand. And one possibility, as you might have suspected already, is doing so by using graphs.
Representing Boards as Graphs
Let’s talk about a classical way of representing boards using graphs. Take a look at the following problem and try to think of a solution.
This time go a bit further and try to think of a general solution, instead of just solving this particular instance. It’s ok if you can’t, I will show you how to do it soon.
Once again, our brains might identify that there are only two paths between the highlighted squares, and we can easily spot which one is the shortest:
The path shown on the left takes 9 steps while the one on the right takes 11 steps.
But, who defined what a path is in this problem? Who defined which tiles we can move to when standing on a specific tile?
Our brains (or at least mine) intuitively assumed that the possible moves from a given position were the following:
So, as long as we are not trying to go to a “wall” tile, we can move to the left, right, up, or down.
Let’s take this set of movements and the “floor“ tiles and see how they relate to graphs. Assuming that the start and end tiles are also floor tiles, we can number every floor tile arbitrarily like this:
We have 14 “floor” tiles, which can be represented as 14 nodes of a graph. So, what about the edges?
Let’s add an edge between two pairs of nodes if it exists a valid movement between their corresponding tiles on the map. For example, we can add edges between nodes 1 and 2, and also between nodes 13 and 14.
That being said, our problem can be reduced to finding the path with the minimum length between two nodes in an undirected graph.
This is the graph that results from taking every floor tile as a node and adding edges according to the valid moves that we defined:
The problem of finding a path with the minimum length between two nodes is a standard problem in the graph theory domain, and we will learn how to solve it in future posts of this series.
For the moment, let’s go back to our initial problem and try to model it using graphs applying what we learned from this example.
Counting the Rooms
Let’s recall the problem we saw at the beginning of this post:
Let’s number every floor tile, and assume that we have the same possible moves that we described above. That is, from a given tile we can move to the tiles at its right, left, top, and bottom as long as they are not “wall“ tiles.
A possible numbering could be the following:
Translating this map to a graph the same way we did before, we get the following:
And if we were to solve the problem of counting the number of rooms in a graph, we could rephrase that as counting the number of its connected components.
See all the “rooms“ taken to the domain of connected components below:
As you also might suspect, the problem of finding the connected components in an undirected graph is also a standard problem that can be solved by using various graph algorithms.
We will be covering those algorithms and more in future editions of Algorithmically Speaking.
In the meantime, it’s time to try what you’ve learned!
Test Your Skills
I have seen a variety of challenges and puzzles on boards that I would like to share some of them with you today.
I would suggest that you try to focus first on solving them by any means possible and then try to think about how to model this problem using a bit of graph theory.
As I promised before, no more plain-text statements. Here we go:
Problem #1:
Problem #2:
The caption of every image contains a link to Excalidraw where you can solve the problem in a very interactive way. Share your solutions and get a mention in the next edition of the graph theory series.
Conclusions
I hope I was able to keep igniting your passion for graph theory by showing you some basic guidelines on how to model board problems using graphs.
This approach is used in numerous real-life applications (at the top of my mind I can think of numerous examples related to the gaming industry).
Also, I recently stumbled upon this video where I found out about a competition that has been going on for more than 50 years and has a lot to do with boards, mazes, and of course, graphs.
Some takeaways:
Board problems can usually be modeled as graphs by taking some set of tiles as the nodes and the possible moves between the tiles as the edges.
Usually, board games involve tasks such as counting regions, or finding paths which are usually standard problems of the graph theory domain.
The chessboard is a bipartite graph. Do you see it now?
I wish you good luck when solving this week’s challenges. Don’t forget to share your progress with the community!
Here are the winners of the past challenge:
- with this solution.
- with this solution:
If you think this post can be helpful for someone, share it with them. Nothing will make me happier!
See you next week!
Loved the flow and the simplicity of the explanations, but the drawings are really top notch!