Finding Mathematical Optimization in Unexpected Places: Games and Puzzles

Author: Dr. Ed Klotz, Senior Mathematical Optimization Specialist

Optimization problems are all around us, often in unexpected places. In my last blog article, I showed interesting examples of how optimization shows up in the art world.

Now let’s talk about another interesting place where optimization pops up: puzzles. If you’re into games or puzzles, then chances are you’ve seen mathematical optimization in action without even realizing it.

I often find that puzzles are a great way to help explain optimization to those who aren’t familiar with it. Here are a few of my favorite examples.

Game #1: The Matrix: Revisited

First up, here’s a simple game we created at Gurobi. In honor of the most recent installment of The Matrix movie franchise, we dubbed it The Matrix: Revisited.

Let’s unpack what we’re looking at here. First, the green Target Matrix is a square grid of non-negative integers. That’s fixed data, and we have no control over that. Next, the 6 red grids are binary matrices filled with 0 and 1 values. Last up, the blue matrix is the one you can manipulate. It starts blank, filled with zeros.

Your goal is to make copies of the red matrices, add them to the blue matrix, and see how close you can get to the green target matrix. (In this on-demand Tech Talk, you can see more about how this works and possible solutions.)

A simulated scenario with real-world applications

Just like in The Matrix the movie, this simulated scenario has a real-world counterpart. In fact, the logic behind this game is helping save lives. It’s a model used to guide radiation treatment therapy for cancer using a robotic tool called a Cyberknife.

The green target matrix is a grid overlaid on the diseased tissue. The integers in it are the dosage levels for each area of tissue within that grid. Certain areas are more diseased (higher numbers like 8 and 7) and need higher dosage levels. Other areas are completely healthy (0), so you want to avoid dosing those areas with any radiation at all.

The red binary matrices correspond to different angles of the robotic arm that administers the dosage of radiation. There are some constraints to specify how the arm can move and how much dosage it can deliver continuously.

When we make a model like this into a game, it’s an amazing way to visualize optimization in the real world. And, spoiler alert, Gurobi was able to solve this small puzzle with ease.

Game #2: Three-Dimensional Sudoku

Let’s look at another game that ties back to optimization. Most of us are familiar with Sudoku, a 9×9 grid that you need to fill with unique numbers.

Most Sudoku puzzles are easy enough for humans to solve on their own. In fact, that’s the whole point of them. But what if we looked at Sudoku in a whole new way?

Try this variant: Instead of filling numbers in, try taking numbers out. As designed, Sudoku puzzles have only one answer. What are the fewest numbers you can take out before you “jailbreak” the puzzle? Hint: Try removing a couple of numbers that don’t appear as often.

Let’s take it up another level. What if we make a Sudoku grid bigger? Here’s a real-world example we’ve worked on where the grid increased to 17×32. The numbers are swapped out for labels, and there’s also the added complexity of color-coding based on certain conditions.

The addition of coloring creates a third dimension to the puzzle.  Also, the rules for placement of the labels in the grid cells are more complex than the standard Sudoku puzzle. The larger grid size, additional dimensionality, and added complexity make this puzzle much harder to solve than even the most challenging standard Sudoku puzzle.

This puzzle would be quite difficult for most humans to solve quickly, if ever. And yet it’s a puzzle that a team of human planners have worked out every year since 1920. If you recognize this as the date when the National Football League was founded, you get extra points.

It turns out, this is the real-world model the NFL uses to plan their game and broadcasting schedule. The horizontal columns identify the 32 teams in the league, from the Dallas Cowboys (DAL) to the Los Angeles Chargers (LAC). The vertical columns represent the 17 weeks in a season (they’ve since moved to 18 weeks). The black squares are bye weeks, where a team isn’t scheduled to play. And the other colors represent the television network on which a particular game is broadcast, from ESPN to NBC.

Using this model, the NFL planners can come up with compelling schedules, with the biggest, most exciting games broadcast to the biggest audiences. Gurobi Optimizer helps them get there, in a fraction of the time that they can figure out a compelling schedule themselves. For more about this story, see our NFL case study.

Game #3: Slitherlink

Another interesting puzzle is Slitherlink, also known as the Traveling Salesman problem. Your job is to connect the dots in a single loop, using the fewest number of lines. The numbers are constraints: how many lines can touch a particular square.

This sort of optimization model can be used in all sorts of real-world scenarios, from how Google Maps helps plan the most efficient route between two points or how delivery services figure out which routes their trucks take each day.

Game #4: Rectangle Packing Game

With this game, the objective is to rearrange the rectangles, in order to minimize the amount of space being used, without letting the rectangles overlap. Using your mouse, you can try rearranging the rectangles into different configurations. As you do, you’ll see your score (measured by the area of the smallest rectangular boundary containing the individual rectangles) in the lower-left corner. The lower the score, the better you’re doing.

Once you think you’ve achieved the most efficient layout, you can let the Gurobi Optimizer give it a try. In less than a second, Gurobi will show you the optimal way to arrange the rectangles.

As you may have guessed by now, this simple and fun game has real-life applications. For example, arranging hardware components on a chip—where the components need to be as close as possible, in order to speed up communication.

It also applies to situations like bin-packing design, two-dimensional job scheduling, and positioning machines on a shop floor, among others. To see the game in action, and learn more about its real-life applications, check out our Tech Talk, Converting Weak to Strong MIP Formulations.

Game #5: Burrito Optimization Game

This game is one we created in-house, for use as an educational tool. It introduces players to the idea of mathematical optimization—teaching them a little about what optimization can do, what sorts of problems it can solve, why someone might want to use it, and what advantages it has over manual trial-and-error approaches.

The goal of the game is to place burrito trucks to serve hungry customers throughout the city, while maximizing your profit. Truck placement has to be carefully planned, because every truck has a cost—but its ability to earn revenue depends on how close it is to potential customers. For example, on some days, special events increase the demand in some regions of the city; on other days, the weather affects customers’ willingness to walk to a burrito truck.

You can play the Burrito Optimization game for free (you’ll just need to create an account). And be sure to check out the Teaching Guide, for more info behind the methodology.

Get Inspired

By turning optimization into games like these, we can consider problems from new angles, in thousands of real-world scenarios. This more visual approach to optimization models can help explain the importance of mathematical optimization and the meaning of individual models to those less familiar with the algebraic representations or underlying mathematical foundations.

For more about how optimization can help you solve puzzles of all sorts, watch our recent Tech Talks: Grab Bag of Interesting and Unusual Optimization Applications, as well as Converting Weak to Strong MIP Formulations.