Voltorb Flip: Overanalyzing a Minigame in Pokemon HeartGold and Soul Silver -- Part 1
The Rules of the Voltorb Flip, The Limits of Determinism, and the Two (and a Half) Rules
Occasionally, I let nostalgia carry me back to the video games I played as a kid. One of these is, of course, Pokemon. I have fond memories of my brother and I arguing over the best starter pokemon for our very first Game Boy game, Pokemon Emerald. Ultimately, he won the argument and we chose Torchic, which, in hindsight, was unambiguously the correct choice.
Recently, I was playing a fan-made game inspired by Emerald, called Pokemon Reborn. It’s much harder than the original Pokemon games and I highly recommend playing it to any fans of the older Pokemon games, but more importantly, it has a Game Corner.
The Game Corner is a lovely children’s gambling establishment that has been a feature of all Pokemon games that I ever played, and it usually contains something like slot machines. But in HeartGold and SoulSilver, pictured above, as well as Pokemon Reborn, the Game Corner has a much more interesting game, called Voltorb Flip.
The Rules of Voltorb Flip
Voltorb Flip is a cross between Sudoku and Minesweeper, with the added twist that it isn’t completely deterministic. The rules are pretty simple.
You begin with 25 blank tiles arranged in a square.
You choose a tile to flip over. Each tile can be a 1, 2, 3, or a Voltorb. If you flip over a 2 tile or a 3 tile, you get a corresponding number of points. A 1 tile is just filler, it doesn’t give you any coins.
But if you flip over a Voltorb, you lose all your coins and have to start over.
Here’s what the full board looked like:
In order to help you choose tiles, you’re provided with some additional information about each board. You’re initially told the number of points in each row/column, as well as the number of Voltorbs. In the board below, we see the top row has 7 points and no Voltorbs, and is thus safe to uncover.
The fifth row has 4 points and 2 Voltorbs. Similarly, the first column has 4 points and 1 Voltorb, and so on and so on.
A board is considered “cleared” (you win) when you’ve revealed all the 2 tiles and 3 tiles, without hitting a Voltorb.
If you clear a board, you advance by one level and your reward increases, as does the number of Voltorbs on the board (the difficulty). If you fail, you drop by a few levels (dropping the difficulty/probability of Voltorbs) and your reward decreases. That’s it!
By itself, this is a fun and engaging minigame, that’s not too hard to become good at if you play it enough. But… what if you needed LOTS of coins for a very expensive prize, and you really wanted to play the game optimally. In other words, can this game be solved?
The Limits of Determinism
First of all, we need to ask the question: Is this game deterministic? Surprisingly, the answer is sometimes.
Fundamentally, this board has 25 unknown tiles, and we’re given 20 constraints, which are the number of Voltorbs in each row & column, and the total points in each row & column, which I will call the row and column “sums.” From that information alone, we can guess that this game is not always deterministically solvable, but let’s look at a few edge cases to prove it.
Case 1: A deterministic board
Consider the following board (generated in a text editor, because I’m lazy).
This board is completely solvable with no information other than the row sum, column sum, row Voltorbs, and column Voltorbs. Let’s prove it by solving it.
Row 2 has no Voltorbs and a total sum of 5. This is only possible if all tiles are 1. The same logic applies to row 4, and columns 2 and 4.
We have a total of 9 unknown tiles remaining.
Row 3 has no Voltorbs. Since column 1 has two unrevealed Voltorbs, and the middle element of column 1 is eliminated by virtue of row 3 being clear of Voltorbs, the only possible positions for the Voltorbs in column 1 is the first and fifth row. The remaining tile must be a 1, because the column sum is 3. The same logic applies to column 5, and rows 1 and 5.
We’re left with only the middle tile, which must be a 3, because the row sum of row 3 is seven. And voila! The board is solved with no guessing involved.
Why is this board deterministic when I have 25 unknowns and 20 constraints? Symmetry! This board just happened to be (at least) fourfold symmetric, which reduces the number of constraints necessary to completely specify the tile arrangement.
Case 2: A nondeterministic board
Now, consider this (also symmetric) board.
Let’s apply the same logic to solving this board, beginning with a blank.
Rows 2, 3, and 4, and columns 2, 3, and 4, all have no Voltorbs and a sum of 5, and therefore are all 1 tiles.
Now, though, we have a problem. There are two possible boards that remain which satisfy all constraints. They’re both twofold symmetric along the diagonals, but the 3s and Voltorbs swap positions.
There is no way to distinguish between them, and so we have a fifty-fifty chance of winning. This board is nondeterministic.
As a side note, there’s also an interesting intermediate case where the board isn’t deterministic, but the algorithm for winning is, i.e. you cannot determine where the 2 or 3 tiles are precisely, but you can precisely identify the positions of the Voltorbs, and thus check all non-Voltorb tiles, winning the game. The simplest example of this is a board with a single Voltorb.
The Two (and a half) Rules
The two previous examples show that we can get pretty far by just using logic. Let’s formalize some rules. For aesthetic and convenience reasons, let’s define a “line” as either a row or a column, since all the logic that follows will apply equally to both rows and columns. I’m going to follow the naming convention of Evin Jaff and Lane Bohrer's analysis of Voltorb Flip algorithms1, which I recommend reading, by the way! I’ll use some of the data from Jaff et al. in Part 2 when I compare the performance of their algorithms to my naive algorithm (spoiler alert: if I read their paper right, mine is a full 8 percentage points better at a minimum!).
Rule 0.5: Safe House Rule
This rule is so obvious I’m making it half a rule. If any line has no Voltorbs, go ahead and flip over that entire line. You (literally) can’t lose.
Rule 1: 5-Sum Rule
Since we only get points for finding 2 tiles or 3 tiles (1 tiles are filler), and we lose if we flip a Voltorb, then any line with only 1 tiles and Voltorbs is a useless line and can be ignored.
Let’s define the “characteristic sum” S of a line as the total number of points in the line P plus the number of Voltorbs V.
S = P + V
If the characteristic sum S = 5, the only possible tiles in that line are 1 tiles and Voltorbs. This is easily proved by exhaustion — a line with 5 Voltorbs has P = 0, V = 5, 4 Voltorbs and a single 1 tile has P = 1, V = 4, etc.
Thus, any line with a characteristic sum S = 5 can be eliminated.
Rule 2: Exhausted Reward Rule (or Extended 5-Sum Rule)
The 5-sum rule can be extended by including known information. Let’s consider the following line:
We have three tiles remaining, two of which are Voltorbs. Since we have 4 points revealed already, a single 1 tile remains unflipped, along with the two Voltorbs. Thus, none of those remaining tiles are useful to us, and this line can also be ignored.
Let’s formalize this. Let x be the number of 1 tiles, y the number of 2 tiles, z the number of 3 tiles, and V the number of Voltorb tiles. x, y, z, and V are all positive integers. The total number of tiles is five:
x + y + z + V = 5.
The total number of points P in the line is:
P = x + 2 y +3 z.
Subtracting those two equations and rearranging, we find:
P + V - 5 = y + 2 z.
We recognize P + V as S, our characteristic line sum.
S - 5 = y + 2 z
Now, let’s define yR as the number of revealed 2 tiles, and yH as the number of hidden 2 tiles. Similarly, zR is the number of revealed 3 tiles, and zH the number of hidden 3 tiles. We substitute y = yR + yH, z = zR + zH into our equation, and put all the known information on the left hand side.
S - 5 - yR - 2 zR = yH + 2 zH
We’re going to define that left hand side as R, the “reward.”
R = S - 5 - yR - 2 zR
If the reward value R of any line equals 0, that line is “exhausted,” i.e. only 1 tiles and Voltorbs remain. Let’s try it out on two examples.
Example 1:
This line has R = 5 + 2 - 5 - 0 - 2*1 = 0. No reward remains in this line —> all tiles are either 1s or Voltorbs.
Example 2:
This line has a characteristic sum S of 6, and a reward R of 1. Therefore:
1 = yH + 2 zH
Because the variables yH and zH must be positive integers, this equation belongs to a class of equations known as Diophantine Equations, which become very nontrivial very quickly as the complexity of the equations increase. If you’ve ever seen those “math-with-fruits” memes on Facebook, you’re already familiar with these sorts of equations.
Fortunately for us, our equation is so easy we don’t need any sophisticated mathematical machinery — the only possible solution is yH = 1, zH = 0. There is exactly one 2 tile hidden somewhere in this line. If we find the 2 tile, the remaining reward is exhausted, and we can eliminate that line.
The Exhausted Reward rule states: Calculate R = S - 5 - yR - 2 zR for each line, where yR and zR are the number of revealed 2 and 3 tiles in the line. If R = 0, the reward is exhausted and that line can be eliminated.
Given a characteristic sum S, how many 2 tiles and/or 3 tiles can exist in that line?
Here’s a handy table of all possible cases:
How far can these rules take us?
Pretty far! Let’s try them out.
On this board, we immediately apply the Safe House rule, flipping columns 1 and 4, and row 4.
Next, we apply the 5-Sum rule, locating lines with characteristic sum (that’s points + Voltorbs) equal to 5, and eliminate those lines. Fortunately, Pokemon provides a helpful “memo” function for marking tiles as eliminated. All tiles that must contain either a 1 or a Voltorb will be marked with a little yellow Voltorb.
Finally, we apply the Exhausted Reward rule. Column 2 has a characteristic sum S = 6, and one 2 tile has been revealed, and so its reward R = 0. Eliminate it. Column 5 has S = 7, with one 3 tile revealed, and so R = 0 there too. Finally, row 3 has S = 6 and we’ve already found the 2 tile, so we can also eliminate that row.
After all the eliminations, only a single tile remains. From the Exhausted Reward rule, we can see that the remaining square must contain a 2 tile. This board was deterministic, and we solved it perfectly!
However, not all boards are deterministic, as we saw earlier.
Eventually, we have to start guessing, and that’s where the problems begin. And by problems, I mean Python code. In Part 2 of my series on Voltorb Flip, we’re going to design and code an algorithm that solves ~71% of boards on the highest difficulty setting.
E Jaff, L Bohrer. Voltorb Flip Algorithm Analysis. 2021. https://evinjaff.github.io/papers/VoltorbFlip.pdf.