How to "solve" Voltorb Flip using an algorithm

July 06, 2022

I thought it'd be fun to write an algorithm to "solve" the Voltorb Flip mini game from the game corner in Pokemon Heart Gold/Soul Silver.

What is Voltorb Flip?
Exploring the Problem: 2x2 Reductions
Writing a Solver
From Solutions to Probabilities
The Completed Voltorb Flip Probability Tool

What is Voltorb Flip?

Voltorb Flip is a mini game played at the game corner in Celadon in Pokemon Heart Gold/Soul Silver. It’s a bit like a mix of Minesweeper and Sudoku. The player is given a five-by-five grid of unknown tiles, and information about the count of Voltorbs and the sums of numbers for each row and column. Using that information, the player flips the tiles to reveal either a Voltorb, which ends the game with no prize, or 1, 2 or 3. The prize is a number of coins equal to all the numbers revealed multiplied together.

It looks something like this:

A screenshot of Voltorb Flip, courtesy of Bulbapedia

I created a web version you can play to get a feel:

Game over! Click anywhere to try again...

... x1, ... x2, ... x3 coins!

Game Over! 0 coins!

Total Coins

00000

Coins Collected in Current Game

00000

The game is primarily based on chance, but there is enough information that the player can increase their chances using some strategies. It’s pretty easy to figure out some of these strategies intuitively, but I wanted to know if there was a way some math could help me out. I wanted to know:

What is the probability that a given tile is a Voltorb?

Also, what is the probability of a tile being a 2x coin multiplier or a 3x coin multiplier? Is a given puzzle solvable? How many possible solutions are there?

Exploring the Problem: 2x2 Reductions

With problems like this, it helps to break it down into more understood cases first. Let’s look only at the probability of each tile being a Voltorb, to keep it simple for now.

When talking about the puzzles, I’ll refer to the number tiles as “coin multipliers” as they are used to multiply the coins you win from the game. The game tells you the sum of all the coin multipliers in a row or column (the number on top), which I’ll refer to as the “sum of coin multipliers constraint”, and it tells you the total count of Voltorbs for a row or column (the number next to the Voltorb icon), which I’ll refer to as the “Voltorb constraint”. I’ll say “constraints” when talking about them both.

Example 1: “Oops, All Voltorbs!”

Let’s take a look at the following contrived puzzle:

		0 2
1	1	2 0
1 1	1 1

It’s straightforward to conclude that both tiles in the first row must be Voltorbs - the first row must have two Voltorbs and there are only two tiles, so the probability of those two tiles being Voltorbs is 100%.

		0 2
1	1	2 0
1 1	1 1

The same follows for the second row but in the inverse: There’s no Voltorbs in second row, so the probability of either tile in the second row being a Voltorb is 0%.

		0 2
1	1	2 0
1 1	1 1

This is the only solution to this puzzle. We know the puzzle must fit the constraints, and this is the only way it fits, therefore everything is certain - either 0% or 100%.

Example 2: “Find the Voltorb”

Keep that last example in mind while we look at another one:

1	1	2 0
1		1 1
2 0	1 1

Looking at the first row only, we know there can’t be any Voltorbs since there are no Voltorbs in that row:

1	1	2 0
1		1 1
2 0	1 1

Looking at the first column only, we know there can’t be any Voltorbs since there are no Voltorbs in that column:

1	1	2 0
1		1 1
2 0	1 1

Therefore, the Voltorb has to be in the last remaining tile - with 100% probability:

1	1	2 0
1		1 1
2 0	1 1

Once again, this puzzle had a single possible solution - this has to be the solution, as we deduced it without any assumptions.

Example 3: “Coin Flip”

Now, finally, for a slightly trickier example:

1		1 1
	1	1 1
1 1	1 1

What is the probability that the tile in the first row, first column is a Voltorb?

Let’s start by looking only at the first row:

1		1 1
	1	1 1
1 1	1 1

There’s one Voltorb in that row, and two tiles. With that information alone, there’s a 50% chance that the Voltorb is in the first column, and a 50% chance it’s the second column.

Now let’s look at the only first column :

1		1 1
	1	1 1
1 1	1 1

There’s one Voltorb in this column, and two tiles. With this information alone, there’s a 50% chance that the Voltorb is in the first row, and a 50% chance it’s in the second row.

Back to the original question: Can we use those probabilities to determine the probability of the first tile being a Voltorb?

1		1 1
	1	1 1
1 1	1 1

There’s a 50% chance that it’s the Voltorb of the first row, and there’s a 50% chance it’s the Voltorb of the first column.

One might assume that means we can simply multiply 50% * 50% = 25% to get the probability that it’s a Voltorb. But that would only work for independent events, ie if the probability that tile is one of the Voltorbs for that row were independent from the probability that it’s one of the Voltorbs for that column.

This is clearly not the case. If a tile is a Voltorb for the row it’s in, it also must be a Voltorb for the column it’s in. Likewise, if the tile is not a Voltorb for its row, it’s also not a Voltorb for its column. The occurrence of one of these events influences the probability of the other, meaning they are dependent on each other.

To put this in more mathy terms:

Two events $A$ and $B$ are independent if the the probability of $A$ given $B$ occurred (denoted $P(A|B)$ ) is equal to the probability of $A$ . (denoted $P(A)$ ):

P(A|B) = P(A)

The probability of the first tile in the example is the one Voltorb allowed for the first row is $P(A)=50\%$ . The probability of that tile being the Voltorb for the first column is $P(B)=50\%$ . The probability that it’s the Voltorb of the first row given it’s the Voltorb for the first column is $P(A|B)=100\%$ . Therefore, since $P(A|B) \neq P(A)$ , these events are not independent.

So instead of getting to use some fancy math shortcuts, we have to use the definition of probability:

The extent to which an event is likely to occur, measured by the ratio of the favorable cases to the total number of cases possible

P(A) = \frac{\#\ of\ possible\ cases\ where\ A\ occurs}{total\ \#\ of\ possible\ cases}

For our puzzle, the “total number of cases possible” is actually the count of all possible solutions to the puzzle, and the count of the “favorable cases” in our example is the count of solutions that a tile is Voltorb. (Don’t get hung up on the term “favorable” - Voltorbs are favorable in the context where you’re seeking them!)

In our earlier examples (Example 1 and Example 2) that’s what did: We found the number of possible solutions in which a certain tile was a Voltorb, and divided by the total number of possible solutions. It just so happened the total number of possible solutions was 1 for both of them, which isn’t the case for this example.

To start finding possible solutions, let’s try make an assumption about what lies underneath one of the tiles.

Let us suppose the tile in the first row, first column is a Voltorb:

	1	1 1
1		1 1
1 1	1 1

There’s only one Voltorb allowed in the first row, so the other tile must be a coin multiplier.

	1	1 1
1		1 1
1 1	1 1

The same follows for the first tile of the second row - there’s only one Voltorb allowed in that column and we’ve already placed one, so it’s not a Voltorb:

	1	1 1
1		1 1
1 1	1 1

Lastly, the final tile must be a Voltorb to satisfy the Voltorb constraints for that row and column:

	1	1 1
1		1 1
1 1	1 1

We didn’t have any other choices for tiles, so this must be the only solution if the first tile is a Voltorb.

Now, let’s try when the first tile is not a Voltorb - let’s say it’s a 1x coin multiplier:

1		1 1
	1	1 1
1 1	1 1

Then, the next tile in that row must be a Voltorb, because the first row needs to have a Voltorb in it:

1		1 1
	1	1 1
1 1	1 1

The same goes for the second tile in the first column, as that column needs one Voltorb:

1		1 1
	1	1 1
1 1	1 1

And lastly, the final tile can’t be a Voltorb, as that would violate both the row and column constraint on the number of Voltorbs:

1		1 1
	1	1 1
1 1	1 1

We were forced into one possible option at every step, so this is the only possible solution if the first tile is a 1x coin multiplier.

Thus there are only two possible solutions to this puzzle - in one of them, the first row, first column tile is a Voltorb, and in the other, it is not. Therefore the odds of a Voltorb being in the first row, first column is 50%.

P(V_{(1,1)}) = \frac{\#\ possible\ solutions\ where\ (1,1)\ is\ a\ Voltorb}{total\ \#\ of\ solutions} = \frac{1}{2}

Writing a Solver

The takeaway from our investigation is that we do not have independent events, and we have to get all possible solutions to the puzzle to determine the probabilities of each tile being a Voltorb. But how do we even begin to program such a solver? How would we find even one solution? Let’s think back to our steps in Example 3. We had a choice for the first tile, so we just picked one possibility and tried to solve the rest of the puzzle given what we chose. Then, when we solved the puzzle, we went back and switched our choice to find another solution.

The key here is to do this repeatedly - every time we encounter a choice where the tile could be multiple things, choose one of them and continue. If we ever can’t meet the constraints, we know that one of our choices is incorrect. In those cases, we go back to our last choice, choose something else, and try to solve the puzzle with that new choice.

Trial and Error

Let’s try this on a new puzzle, this time a 3x3:

	1	1	2 1
1			1 2
	1		1 2
1 2	2 1	1 2

Ok, time to take our first step. We can assume the first tile is a Voltorb as both the row and column constraints allow it:

	1	1	2 1
1			1 2
	1		1 2
1 2	2 1	1 2

That’s the only Voltorb in the first row, so the rest must be coin multipliers (we’ll assume all coin multipliers are 1x coin multipliers for now - just treat this as “not Voltorb”):

	1	1	2 1
1			1 2
	1		1 2
1 2	2 1	1 2

Then, the first column of the second row we have a choice again, as both the column and row constraints allow for a Voltorb here and there’s still a coin multiplier available for each. Let’s assume it’s a Voltorb for now:

	1	1	2 1
			1 2
	1		1 2
1 2	2 1	1 2

Again we’re presented with a choice between a Voltorb or coin multiplier. Let’s arbitrarily assume the middle tile is a Voltorb, noting it’s allowed by both column and row constraints:

	1	1	2 1
			1 2
	1		1 2
1 2	2 1	1 2

With the assumptions we’ve made so far, last tile of the second row cannot be a Voltorb since the row only allows for two:

	1	1	2 1
		1	1 2
	1		1 2
1 2	2 1	1 2

The bottom left tile has to be a coin multiplier, as there are no more Voltorbs allowed in the first column:

	1	1	2 1
		1	1 2
1	1		1 2
1 2	2 1	1 2

The bottom middle tile must be a coin multiplier as the second column also doesn’t allow for more Voltorbs. But the third row needs two Voltorbs! There’s nothing we can do to satisfy the constraints.

	1	1	2 1
		1	1 2
1	1		1 2
1 2	2 1	1 2

This means one of our assumptions was wrong. We’ll have to go backwards, undoing all the work since the last assumption. The last assumption was that the middle tile was Voltorb. This time, let’s assume the middle tile is a coin multiplier:

	1	1	2 1
	1		1 2
	1		1 2
1 2	2 1	1 2

Then the next tile must be a Voltorb to meet the row constraint:

	1	1	2 1
	1		1 2
	1		1 2
1 2	2 1	1 2

And the bottom left tile must still be a coin multiplier to meet the column constraint, while the remaining two tiles in the last row must be Voltorbs to meet the row (and column) constraints:

	1	1	2 1
	1		1 2
1			1 2
1 2	2 1	1 2

We found a solution!

It’s not the only solution, however! To find the rest of the solutions, we have to go back to our last assumption, change it, and see if the puzzle can be solved. We’ll keep repeating this until we can’t change any more assumptions. I’ll leave the step-by-step as an exercise for the reader. Here are the possible solutions for this puzzle:

	1	1	2 1
	1		1 2
1			1 2
1 2	2 1	1 2

	1	1	2 1
1			1 2
	1		1 2
1 2	2 1	1 2

1		1	2 1
	1		1 2
	1		1 2
1 2	2 1	1 2

1	1		2 1
		1	1 2
	1		1 2
1 2	2 1	1 2

1	1		2 1
	1		1 2
		1	1 2
1 2	2 1	1 2

What about coin multipliers?

So far, we’ve only been talking about Voltorbs, but we actually have more information to work with: the sum of coin multipliers per row and column. We also have more unknowns about the tiles once we stop assuming they’re all 1x coin multipliers. It doesn’t really do any good to uncover a 1x coin multiplier in the game when you’re playing - your winnings won’t change. You really want to uncover all the 2x and 3x coin multipliers.

We could do the same thing we did before, and try every possibility manually and see how it goes later, but there are some intuitive rules that we could follow for some early optimization to skip some cycles and be a little faster. Take this example row for instance:

A naive, simple brute force solver algorithm would try everything and see if it works. That means trying all possible values (there are four: a Voltorb, 1x, 2x or 3x coin multiplier) for each tile (there are 5 of them). This means trying ~ $4^5$ different combinations for just one row - and intuitively, you likely know already that there’s only 5 possible solutions!

We can likely intuit there are only 5 possible solutions because we can see that this row can’t have any 2x or 3x multipliers and have the coin multipliers add up the 4 specified in the constraint. But to help illustrate why that is, let’s just see what happens if we assume the first tile is a 2x multiplier:

The next tile is a choice, so let’s assume the it’s a Voltorb:

Now we can’t place any more Voltorbs, let’s arbitrarily assume the next tile is a 2x multiplier:

For the next tile after that, we can’t place a Voltorb nor a coin multiplier, as we’ve already hit the Voltorb count and the sum of coin multipliers constraints for the row. There’s no solution with these assumptions! Let’s change our last assumption to a 1x coin multiplier:

Then the next tile must be a 1x coin multiplier, as anything 2x or more would break the sum of coin multipliers constraint for the row:

And once again, there’s no valid option to choose for the last tile, and there’s no solution. We have to go back to our last assumption… and so on, and so forth. This could take a while!

Our brute force algorithm will handle this appropriately evenutally, but it shouldn’t even attempt solutions with 2x or 3x coin multipliers for this row at all, which could save a ton of iterations on our solver. Without that optimization, it will keep moving the coin multipliers and Voltorb around and continue to try to solve the row with the 2x and 3x multipliers multiple times. In order to avoid this, we need to figure out what the maximum coin multiplier value is for a given tile so we don’t attempt to choose coin multipliers that are higher than that.

What is the maximum coin multiplier for a tile?

The way to figure out the maximum coin multiplier for a tile is to assume all the remaining unknown tiles are the minimum value they can be. For instance, looking at our example again, if we want to know the max coin multiplier for the first tile, we have to assume one Voltorb and three 1x coin multipliers for the remaining tiles:

The sum of all coin multipliers in the row should be 4, and minimum possible sum of all other tiles is 3. Therefore the max value of this cell is a 1x coin multiplier.

Looking at another example:

We know three of these must be Voltorbs, and assume the last is the minimum 1x coin multiplier:

The “sum of coin multipliers” constraint for the row less the minimum sum of all other tiles is $4 - 1 = 3$ . The max coin multiplier for this cell must then be a 3x coin multiplier.

To calculate this in code, we’ll need to keep track of some running totals while we’re running the solver. We’ll need to know the current count of Voltorbs chosen so far for the row or column, as well as the sum of the coin multipliers chosen so far for the row or column. With those running totals and the original constraints, we can sort out an equation for the max coin multiplier for a tile:

/**
 * Gets the maximum coin multiplier a tile can be for a row or column, given the
 * constraints and current solution state.
 * @param cellsRemaining The count of tiles not yet determined by the solver
 *   for the row or column, excluding the tile currently being determined
 * @param runningVoltorbs The running count of Voltorbs determined by the solver
 *  for the row or column
 * @param runningCoinSum The running sum of coin multipliers determined by the
 *  solver for the row or column
 * @param voltorbCount The count of Voltorbs for the row or column
 * @param coinSum The sum of coin multipliers for the row or column
 * @returns the maximum coin multiplier value that tile can be
 */
function getMaxCoinMultiplier(
  cellsRemaining: number,
  runningVoltorbs: number,
  runningCoinSum: number,
  voltorbCount: number,
  coinSum: number
) {
  // Get the count of Voltorbs remaining
  const voltorbsRemaining = voltorbCount - runningVoltorbs

  // Get the count of coin multiplier tiles remaining
  const coinsRemaining = cellsRemaining - voltorbsRemaining

  // Get the minimum sum of coin multipliers for this row or column
  const minCoinSum = runningCoinSum + coinsRemaining * 1

  // The max is when all the other coin multipliers are minimized
  // Returning 0 will mean that it cannot be a coin multiplier
  return Math.max(Math.min(coinSum - maxCoinSum, 3), 0)
}

What is the minimum coin multiplier for a tile?

Great! We have a function that can help us find the maximum coin multiplier for a given tile. This begs the question, however: what is the minimum coin multiplier for a given tile?

For example, while running our solver, let’s say we’re in the following state:

Note that if we assume the highlighted cell is a 1x coin multiplier, then there’s no possible values for the next two cells to get us up to the coin multiplier sum constraint for the row:

Much like the above where we found the maximum value for a coin multiplier by assuming the rest of the tiles were the minimum coin multiplier, we’ll find the minimum coin multiplier by assuming the rest of the tiles are the maximum coin multiplier:

Then just like before, the difference between the coin multiplier constraint and our sum is the our boundary for the coin value of the tile in question. In this case, that’s $8 - 6 = 2$ .

/**
 * Gets the minimum coin multiplier a tile can be for a row or column, given the
 * constraints and current solution state.
 * @param cellsRemaining The count of tiles not yet determined by the solver
 *   for the row or column, excluding the tile currently being determined
 * @param runningVoltorbs The running count of Voltorbs determined by the solver
 *  for the row or column
 * @param runningCoinSum The running sum of coin multipliers determined by the
 *  solver for the row or column
 * @param voltorbCount The count of Voltorbs for the row or column
 * @param coinSum The sum of coin multipliers for the row or column
 * @returns the minimum coin multiplier value that tile can be
 */
function getMinCoinMultiplier(
  cellsRemaining: number,
  runningVoltorbs: number,
  runningCoinSum: number,
  voltorbCount: number,
  coinSum: number
) {
  // Get the count of Voltorbs remaining
  const voltorbsRemaining = voltorbCount - runningVoltorbs
  // Get the count of coin multiplier tiles remaining
  const coinsRemaining = cellsRemaining - voltorbsRemaining
  // Get the maximum sum of coin multipliers for this row or column
  const maxCoinSum = runningCoinSum + coinsRemaining * 3
  // The min is when all the other coin multipliers are maximized
  return Math.max(Math.min(coinSum - maxCoinSum, 3), 1)
}

Getting the Coin Multiplier Bounds

Note how similar getMaxCoinMultiplier and getMinCoinMultiplier are. We could probably simplify things and optimize a bit by calculating them together. Also, the naming was getting confusing, so I extracted out a new type, Constraint, that can be used for both the game’s constraints and our running totals:

export type Constraint = {
  voltorbCount: number
  coinSum: number
}

/**
 * Gets the minimum and maximum coin multiplier a tile can be for a row or
 * column given the constraints and current solution totals.
 * @param cellsRemaining The count of tiles not yet determined by the solver
 *   for the row or column, excluding the tile currently being determined
 * @param runningTotal The running count of Voltorbs and sum of coin multipliers
 *  determined by the solver for the row or column
 * @param constraint The count of Voltorbs and sum of coin multipliers
 *  defined by the puzzle constraints
 * @returns [min, max] inclusive bounds on the possible values for a 
 *  coin multiplier for a tile
 */
function getCoinMultiplierBounds(
  cellsRemaining: number,
  runningTotal: Constraint,
  constraint: Constraint
) {
  // Get the count of Voltorbs remaining
  const voltorbsRemaining = constraint.voltorbCount - runningTotal.voltorbCount
  // Get the count of 3x coin multipliers remaining
  const coinsRemaining = cellsRemaining - voltorbsRemaining
  // Get the minimum sum of coin multipliers for this row or column
  const minCoinSum = runningTotal.coinSum + coinsRemaining
  // Get the maximum sum of coin multipliers for this row or column
  const maxCoinSum = runningTotal.coinSum + coinsRemaining * 3
  // The min is when all the other coin multipliers are maximized
  const minCoin = Math.max(Math.min(constraint.coinSum - maxCoinSum, 3), 1)
  // The max is when all the other coin multipliers are minimized
  // Returning 0 will mean that it cannot be a coin multiplier
  const maxCoin = Math.max(Math.min(constraint.coinSum - minCoinSum, 3), 0)
  return [minCoin, maxCoin]
}

Coding the Solver

Ok, so now we have some way to minimize the excess iterations of our original “simple” solver. To reiterate our earlier strategy, we’re going to go through our game grid tile by tile, assuming all the different possibilities for each tile that fit the constraints and any previous assumptions. If we can pick a value for each tile that satisfies the constraints, then we’ve found a solution! If not, we go back to the last assumption and change it.

In order to be able to try all the different valid values, we’ll do a recursive algorithm. Each call of the inner recursive function will be to determine the valid values of a tile given a working solution.

We’ll start by initializing our working solution to a 2D array representing the game grid. The possible values will be 0, 1, 2, 3 or null, where 0 is a Voltorb and null is an undetermined cell. Initially, our working solution is completely undetermined, so every value will be null. The solver then should call the inner recursive function for the first tile at $(0, 0)$ with working solution.

// Types
export const allCellValues = [0, 1, 2, 3] as const
export type CellValue = typeof allCellValues[number]
export type Constraint = {
  voltorbCount: number
  coinSum: number
}

/**
 * Utility to create 2D arrays with default values filled (without references)
 * @param rows the number of rows
 * @param columns the number of columns
 * @param fill the value to fill with
 * @returns a new 2D array with the values filled
 */
export function create2DArray<T extends object | null | undefined>(
  rows: number,
  columns: number,
  fill: T
) {
  const result: T[][] = []
  for (let row = 0; row < rows; row++) {
    result[row] = []
    for (let col = 0; col < columns; col++) {
      result[row][col] = fill === Object(fill) ? { ...fill } : fill
    }
  }
  return result
}

/**
 * Inner recursive call for solving the game in the given state
 * @param curRow the row of the cell being determined
 * @param curCol the column of the cell being determined
 * @param currentSolution the working solution so far
 * @param rowConstraints the Voltorb count and coin sum for each row
 * @param colConstraints the Voltorb count and coin sum for each column
 * @returns an array of solutions for the given state
 */
function _solve(
  curRow: number,
  curCol: number,
  currentSolution: (CellValue | null)[][],
  rowConstraints: Constraint[],
  colConstraints: Constraint[]
) {
  // TODO: Implement _solve()
}

/**
 * Gets all possible solutions to a puzzle defined by the constraints
 * @param rowConstraints the Voltorb count and coin sum for each row
 * @param colConstraints the Voltorb count and coin sum for each column
 */
export function solve(
  rowConstraints: Constraint[],
  colConstraints: Constraint[]
) {
  return _solve(
    0,
    0,
    create2DArray(rowConstraints.length, colConstraints.length, null),
    rowConstraints,
    colConstraints
  )
}

We’ll determine the possible values for the current tile (which I refer to as “cell” in the code) by getting its minimum and maximum coin multiplier value (which can be Voltorbs, not just coin multipliers!), as well as figuring out if it can be a Voltorb.

First we get our running totals of Voltorbs and the sum of coin multipliers for the current row and column, as they’re needed to determine the maximum possible value.

function _solve(
  curRow: number,
  curCol: number,
  currentSolution: (CellValue | null)[][],
  rowConstraints: Constraint[],
  colConstraints: Constraint[]
) {
  // Get running totals  let rowRunningTotals: Constraint = { voltorbCount: 0, coinSum: 0 }  let colRunningTotals: Constraint = { voltorbCount: 0, coinSum: 0 }  for (let row = 0; row < rowConstraints.length; row++) {    colRunningTotals.coinSum += currentSolution[row][curCol] ?? 0    colRunningTotals.voltorbCount += currentSolution[row][curCol] === 0 ? 1 : 0  }  for (let col = 0; col < colConstraints.length; col++) {    rowRunningTotals.coinSum += currentSolution[curRow][col] ?? 0    rowRunningTotals.voltorbCount += currentSolution[curRow][col] === 0 ? 1 : 0  }}

Optimization Sidenote: Calculating the running totals on each iteration does affect runtime slightly as it means we’re doing $n$ operations per iteration over the grid, but in practice this grid isn’t that large (the game is always 5x5). Passing in the running totals and incrementing it on every new value has the same impact as we’d need to copy both the arrays anyway. It’s still more advantageous to calculate these running totals every iteration than it is to try each and every value like our simple brute force solver would have. There’s probably some clever memoization technique to be employed here, and it’s likely possible to reduce the recursive call down to some while loop implementation, but I think this is the code that’s most intuitive.

Now that we have the running totals for the row and column, we can use them to get the min and max coin multiplier value for the current cell using the method we made in the last section:

/** * Gets the minimum and maximum coin multiplier a tile can be for a row or * column given the constraints and current solution totals. * @param cellsRemaining The count of tiles not yet determined by the solver *   for the row or column, excluding the tile currently being determined * @param runningTotal The running count of Voltorbs and sum of coin multipliers *  determined by the solver for the row or column * @param constraint The count of Voltorbs and sum of coin multipliers *  defined by the puzzle constraints * @returns [min, max] inclusive bounds on the coin value for the tile */function getCoinMultiplierBounds(  cellsRemaining: number,  runningTotal: Constraint,  constraint: Constraint) {  // Get the count of Voltorbs remaining  const voltorbsRemaining = constraint.voltorbCount - runningTotal.voltorbCount  // Get the count of 3x coin multipliers remaining  const coinsRemaining = cellsRemaining - voltorbsRemaining  // Get the minimum sum of coin multipliers for this row or column  const minCoinSum = runningTotal.coinSum + coinsRemaining  // Get the maximum sum of coin multipliers for this row or column  const maxCoinSum = runningTotal.coinSum + coinsRemaining * 3  // The min is when all the other coin multipliers are maximized  const minCoin = Math.max(Math.min(constraint.coinSum - maxCoinSum, 3), 1)  // The max is when all the other coin multipliers are minimized  // Returning 0 will mean that it cannot be a coin multiplier  const maxCoin = Math.max(Math.min(constraint.coinSum - minCoinSum, 3), 0)  return [minCoin, maxCoin]}
function _solve(
  curRow: number,
  curCol: number,
  currentSolution: (CellValue | null)[][],
  rowConstraints: Constraint[],
  colConstraints: Constraint[]
) {

  // Get running totals. These could be copied and passed on each call for more
  // optimization, but that's not super necessary for this demo
  let rowRunningTotals: Constraint = { voltorbCount: 0, coinSum: 0 }
  let colRunningTotals: Constraint = { voltorbCount: 0, coinSum: 0 }
  for (let row = 0; row < rowConstraints.length; row++) {
    colRunningTotals.coinSum += currentSolution[row][curCol] ?? 0
    colRunningTotals.voltorbCount += currentSolution[row][curCol] === 0 ? 1 : 0
  }
  for (let col = 0; col < colConstraints.length; col++) {
    rowRunningTotals.coinSum += currentSolution[curRow][col] ?? 0
    rowRunningTotals.voltorbCount += currentSolution[curRow][col] === 0 ? 1 : 0
  }

  // Get the min and max coin multiplier for the current cell  const [minRowCoin, maxRowCoin] = getCoinMultiplierBounds(    rowConstraints.length - curCol - 1,    rowRunningTotals,    rowConstraints[curRow]  )  const [minColCoin, maxColCoin] = getCoinMultiplierBounds(    colConstraints.length - curRow - 1,    colRunningTotals,    colConstraints[curCol]  )  const minCoin = Math.max(minRowCoin, minColCoin)  const maxCoin = Math.min(maxRowCoin, maxColCoin)}

We know what the possible coin multiplier values the tile can have, but we need to know whether it can be a Voltorb, too. To do that all we have to do is check that we haven’t met the Voltorb constraint yet for the row or column.

function _solve(
  curRow: number,
  curCol: number,
  currentSolution: (CellValue | null)[][],
  rowConstraints: Constraint[],
  colConstraints: Constraint[]
) {
  // ...

  // Get the min and max coin multiplier for the current cell
  const [minRowCoin, maxRowCoin] = getCoinMultiplierBounds(
    rowConstraints.length - curCol - 1,
    rowRunningTotals,
    rowConstraints[curRow]
  )
  const [minColCoin, maxColCoin] = getCoinMultiplierBounds(
    colConstraints.length - curRow - 1,
    colRunningTotals,
    colConstraints[curCol]
  )
  const minCoin = Math.max(minRowCoin, minColCoin)
  const maxCoin = Math.min(maxRowCoin, maxColCoin)

  // Check the Voltorb count constraint to see if the tile can be a Voltorb  const canBeVoltorb =    colRunningTotals.voltorbCount < colConstraints[curCol].voltorbCount &&    rowRunningTotals.voltorbCount < rowConstraints[curRow].voltorbCount}

With that, we now know every possible value the tile can have. For each value, we’ll make a copy of our current working solution with that value as the current cell value, and call the inner recursive function again with the new working solution and for the next tile.

Optimization Sidenote: Once again sneakily doing a what looks like a very expensive operation ( $O(n^2)$ ) creating the deep copy of the array, but in practice $n = 5$ so we’re only multiplying the number of iterations by 25 so I’m not even going to bother to think about optimizations here (though one could argue there are memory constraints to consider as well, especially as we’re copying and allocating on a recursive stack). Not that not doing the min/max stuff from previous sections, however, would mean getting much closer to the “try everything value, check constraints after” runtime of $4^{25}$ total iterations!

/** * Utility to deeply copy a 2D array * @param array the 2D array to deep copy * @returns a copy of the same array without references */function deepCopy2DArray(array: any[][]) {  const copy = [...array]  for (let i = 0; i < array.length; i++) {    copy[i] = [...array[i]]  }  return copy}
function _solve(
  curRow: number,
  curCol: number,
  currentSolution: (CellValue | null)[][],
  rowConstraints: Constraint[],
  colConstraints: Constraint[]
) {
// Get running totals
  let rowRunningTotals: Constraint = { voltorbCount: 0, coinSum: 0 }
  let colRunningTotals: Constraint = { voltorbCount: 0, coinSum: 0 }
  for (let row = 0; row < rowConstraints.length; row++) {
    colRunningTotals.coinSum += currentSolution[row][curCol] ?? 0
    colRunningTotals.voltorbCount += currentSolution[row][curCol] === 0 ? 1 : 0
  }
  for (let col = 0; col < colConstraints.length; col++) {
    rowRunningTotals.coinSum += currentSolution[curRow][col] ?? 0
    rowRunningTotals.voltorbCount += currentSolution[curRow][col] === 0 ? 1 : 0
  }

  // Get the min and max coin multiplier for the current cell
  const [minRowCoin, maxRowCoin] = getCoinMultiplierBounds(
    rowConstraints.length - curCol - 1,
    rowRunningTotals,
    rowConstraints[curRow]
  )
  const [minColCoin, maxColCoin] = getCoinMultiplierBounds(
    colConstraints.length - curRow - 1,
    colRunningTotals,
    colConstraints[curCol]
  )
  const minCoin = Math.max(minRowCoin, minColCoin)
  const maxCoin = Math.min(maxRowCoin, maxColCoin)

  // Check the Voltorb count constraint to see if the tile can be a Voltorb
  const canBeVoltorb =
    colRunningTotals.voltorbCount < colConstraints[curCol].voltorbCount &&
    rowRunningTotals.voltorbCount < rowConstraints[curRow].voltorbCount

  let allSolutions: CellValue[][][] = []  const nextCol = (curCol + 1) % colConstraints.length  const nextRow = nextCol === 0 ? curRow + 1 : curRow  // Find all solutions when trying values from the min to max coin multipliers  for (let coin = minCoin; coin <= maxCoin; coin++) {    const nextSolution = deepCopy2DArray(currentSolution)    nextSolution[curRow][curCol] = coin    const solutions = _solve(      nextRow,      nextCol,      nextSolution,      rowConstraints,      colConstraints    )    allSolutions = allSolutions.concat(solutions)  }  // Check Voltorbs too, if the current tile can be a Voltorb  if (canBeVoltorb) {    const nextSolution = deepCopy2DArray(currentSolution)    nextSolution[curRow][curCol] = 0    const solutions = _solve(      nextRow,      nextCol,      nextSolution,      rowConstraints,      colConstraints    )    allSolutions = allSolutions.concat(solutions)  }  return allSolutions}

We’re nearly done! We need our base cases to stop the recursion. Note that when there’s no possible values, we’re already returning an empty array, so the “no solution” case is handled. For valid solutions, we know a solution is valid if we’ve reached the end of the grid and have a value in each cell. We need to return the valid solution wrapped as an array so that other solutions can be added as we recurse.

function _solve(
  curRow: number,
  curCol: number,
  currentSolution: (CellValue | null)[][],
  rowConstraints: Constraint[],
  colConstraints: Constraint[]
) {
  // Check base case: we found a solution!  if (curRow === currentSolution.length) {    return [currentSolution as CellValue[][]]  }
  // Get running totals
  let rowRunningTotals: Constraint = { voltorbCount: 0, coinSum: 0 }
  let colRunningTotals: Constraint = { voltorbCount: 0, coinSum: 0 }
  for (let row = 0; row < rowConstraints.length; row++) {
    colRunningTotals.coinSum += currentSolution[row][curCol] ?? 0
    colRunningTotals.voltorbCount += currentSolution[row][curCol] === 0 ? 1 : 0
  }
  for (let col = 0; col < colConstraints.length; col++) {
    rowRunningTotals.coinSum += currentSolution[curRow][col] ?? 0
    rowRunningTotals.voltorbCount += currentSolution[curRow][col] === 0 ? 1 : 0
  }

  // Get the min and max coin multiplier for the current cell
  const [minRowCoin, maxRowCoin] = getCoinMultiplierBounds(
    rowConstraints.length - curCol - 1,
    rowRunningTotals,
    rowConstraints[curRow]
  )
  const [minColCoin, maxColCoin] = getCoinMultiplierBounds(
    colConstraints.length - curRow - 1,
    colRunningTotals,
    colConstraints[curCol]
  )
  const minCoin = Math.max(minRowCoin, minColCoin)
  const maxCoin = Math.min(maxRowCoin, maxColCoin)

  // Check the Voltorb count constraint to see if the tile can be a Voltorb
  const canBeVoltorb =
    colRunningTotals.voltorbCount < colConstraints[curCol].voltorbCount &&
    rowRunningTotals.voltorbCount < rowConstraints[curRow].voltorbCount

  let allSolutions: CellValue[][][] = []  const nextCol = (curCol + 1) % colConstraints.length
  const nextRow = nextCol === 0 ? curRow + 1 : curRow

  // Find all solutions when trying values from the min to max coin multipliers
  for (let coin = minCoin; coin <= maxCoin; coin++) {
    const nextSolution = deepCopy2DArray(currentSolution)
    nextSolution[curRow][curCol] = coin
    const solutions = _solve(
      nextRow,
      nextCol,
      nextSolution,
      rowConstraints,
      colConstraints
    )
    allSolutions = allSolutions.concat(solutions)
  }

  // Check Voltorbs too, if the current tile can be a Voltorb
  if (canBeVoltorb) {
    const nextSolution = deepCopy2DArray(currentSolution)
    nextSolution[curRow][curCol] = 0
    const solutions = _solve(
      nextRow,
      nextCol,
      nextSolution,
      rowConstraints,
      colConstraints
    )
    allSolutions = allSolutions.concat(solutions)
  }

  // Note that if there are no valid coin values, and the tile can't be a   // Voltorb, this returns an empty array already!  return allSolutions}

Okay, we have a solver now! It returns an array of all the possible solutions to the puzzle when you call solve(). Here’s the complete code up through this section:

// Types
export const allCellValues = [0, 1, 2, 3] as const
export type CellValue = typeof allCellValues[number]
export type Constraint = {
  voltorbCount: number
  coinSum: number
}

/**
 * Utility to create 2D arrays with default values filled (without references)
 * @param rows the number of rows
 * @param columns the number of columns
 * @param fill the value to fill with
 * @returns a new 2D array with the values filled
 */
export function create2DArray<T extends object | null | undefined>(
  rows: number,
  columns: number,
  fill: T
) {
  const result: T[][] = []
  for (let row = 0; row < rows; row++) {
    result[row] = []
    for (let col = 0; col < columns; col++) {
      result[row][col] = fill === Object(fill) ? { ...fill } : fill
    }
  }
  return result
}

/**
 * Utility to deeply copy a 2D array
 * @param array the 2D array to deep copy
 * @returns a copy of the same array without references
 */
function deepCopy2DArray(array: any[][]) {
  const copy = [...array]
  for (let i = 0; i < array.length; i++) {
    copy[i] = [...array[i]]
  }
  return copy
}

/**
 * Gets the maximum coin multiplier a tile can be for a row or column, given the
 * constraints and current solution state.
 * @param cellsRemaining The count of tiles not yet determined by the solver
 *   for the row or column, excluding the tile currently being determined
 * @param runningVoltorbs The running count of Voltorbs determined by the solver
 *  for the row or column
 * @param runningCoinSum The running sum of coin multipliers determined by the
 *  solver for the row or column
 * @param maxVoltorbs The max count of Voltorbs for the row or column,
 *   given by the puzzle
 * @param maxCoinSum The max sum of coin multipliers for the row or column,
 *   given by the puzzle
 * @returns the maximum coin multiplier value that tile can be.
 *   If it must be a Voltorb, returns 0.
 */
function getMaxCoinMultiplier(
  cellsRemaining: number,
  runningVoltorbs: number,
  runningCoinSum: number,
  maxVoltorbs: number,
  maxCoinSum: number
) {
  // Get the count of Voltorbs remaining
  const voltorbsRemaining = maxVoltorbs - runningVoltorbs
  // Get the count of 1x coin multipliers remaining
  const minCoinsRemaining = cellsRemaining - voltorbsRemaining
  // Get the minimum sum of coin multipliers for this row or column
  const minCoinSumRemaining = runningCoinSum + minCoinsRemaining
  // The difference between max and min sums is the max coin multiplier
  return Math.max(Math.min(maxCoinSum - minCoinSumRemaining, 3), 0)
}

/**
 * Gets the minimum and maximum coin multiplier a tile can be for a row or
 * column given the constraints and current solution totals.
 * @param cellsRemaining The count of tiles not yet determined by the solver
 *   for the row or column, excluding the tile currently being determined
 * @param runningTotal The running count of Voltorbs and sum of coin multipliers
 *  determined by the solver for the row or column
 * @param constraint The count of Voltorbs and sum of coin multipliers
 *  defined by the puzzle constraints
 * @returns [min, max] inclusive bounds on the coin value for the tile
 */
function getCoinMultiplierBounds(
  cellsRemaining: number,
  runningTotal: Constraint,
  constraint: Constraint
) {
  // Get the count of Voltorbs remaining
  const voltorbsRemaining = constraint.voltorbCount - runningTotal.voltorbCount
  // Get the count of 3x coin multipliers remaining
  const coinsRemaining = cellsRemaining - voltorbsRemaining
  // Get the minimum sum of coin multipliers for this row or column
  const minCoinSum = runningTotal.coinSum + coinsRemaining
  // Get the maximum sum of coin multipliers for this row or column
  const maxCoinSum = runningTotal.coinSum + coinsRemaining * 3
  // The min is when all the other coin multipliers are maximized
  const minCoin = Math.max(Math.min(constraint.coinSum - maxCoinSum, 3), 1)
  // The max is when all the other coin multipliers are minimized
  // Allow returning zero to show that there's no possible coin multiplier here
  const maxCoin = Math.max(Math.min(constraint.coinSum - minCoinSum, 3), 0)
  return [minCoin, maxCoin]
}

/**
 * Inner recursive call for solving the game in the given state
 * @param curRow the row of the cell being determined
 * @param curCol the column of the cell being determined
 * @param currentSolution the working solution so far
 * @param rowConstraints the Voltorb count and coin sum for each row
 * @param colConstraints the Voltorb count and coin sum for each column
 * @returns an array of solutions for the given state
 */
function _solve(
  curRow: number,
  curCol: number,
  currentSolution: (CellValue | null)[][],
  rowConstraints: Constraint[],
  colConstraints: Constraint[]
) {
  // Check base case: we found a solution!
  if (curRow === currentSolution.length) {
    return [currentSolution as CellValue[][]]
  }

  // Get running totals
  let rowRunningTotals: Constraint = { voltorbCount: 0, coinSum: 0 }
  let colRunningTotals: Constraint = { voltorbCount: 0, coinSum: 0 }
  for (let row = 0; row < rowConstraints.length; row++) {
    colRunningTotals.coinSum += currentSolution[row][curCol] ?? 0
    colRunningTotals.voltorbCount += currentSolution[row][curCol] === 0 ? 1 : 0
  }
  for (let col = 0; col < colConstraints.length; col++) {
    rowRunningTotals.coinSum += currentSolution[curRow][col] ?? 0
    rowRunningTotals.voltorbCount += currentSolution[curRow][col] === 0 ? 1 : 0
  }

  // Get the min and max coin multiplier for the current cell
  const [minRowCoin, maxRowCoin] = getCoinMultiplierBounds(
    rowConstraints.length - curCol - 1,
    rowRunningTotals,
    rowConstraints[curRow]
  )
  const [minColCoin, maxColCoin] = getCoinMultiplierBounds(
    colConstraints.length - curRow - 1,
    colRunningTotals,
    colConstraints[curCol]
  )
  const minCoin = Math.max(minRowCoin, minColCoin)
  const maxCoin = Math.min(maxRowCoin, maxColCoin)

  // Check the Voltorb count constraint to see if the tile can be a Voltorb
  const canBeVoltorb =
    colRunningTotals.voltorbCount < colConstraints[curCol].voltorbCount &&
    rowRunningTotals.voltorbCount < rowConstraints[curRow].voltorbCount

  let allSolutions: CellValue[][][] = []
  const nextCol = (curCol + 1) % colConstraints.length
  const nextRow = nextCol === 0 ? curRow + 1 : curRow

  // Find all solutions when trying values from the min to max coin multipliers
  for (let coin = minCoin; coin <= maxCoin; coin++) {
    const nextSolution = deepCopy2DArray(currentSolution)
    nextSolution[curRow][curCol] = coin
    const solutions = _solve(
      nextRow,
      nextCol,
      nextSolution,
      rowConstraints,
      colConstraints
    )
    allSolutions = allSolutions.concat(solutions)
  }

  // Check Voltorbs too, if the current tile can be a Voltorb
  if (canBeVoltorb) {
    const nextSolution = deepCopy2DArray(currentSolution)
    nextSolution[curRow][curCol] = 0
    const solutions = _solve(
      nextRow,
      nextCol,
      nextSolution,
      rowConstraints,
      colConstraints
    )
    allSolutions = allSolutions.concat(solutions)
  }

  return allSolutions
}

/**
 * Gets all possible solutions to a puzzle defined by the constraints
 * @param rowConstraints the Voltorb count and coin sum for each row
 * @param colConstraints the Voltorb count and coin sum for each column
 */
export function solve(
  rowConstraints: Constraint[],
  colConstraints: Constraint[]
) {
  return _solve(
    0,
    0,
    create2DArray(rowConstraints.length, colConstraints.length, null),
    rowConstraints,
    colConstraints
  )
}

/**
 * Filters out solutions that don't match the actual solution
 * @param actualSolution
 * @param potentialSolution
 * @returns true if the values in actualSolution match the potentialSolution
 */
export function filterSolution(
  actualSolution: (CellValue | null)[][],
  potentialSolution: CellValue[][]
) {
  for (let row = 0; row < potentialSolution.length; row++) {
    for (let col = 0; col < potentialSolution[row].length; col++) {
      if (
        actualSolution[row][col] !== null &&
        potentialSolution[row][col] !== actualSolution[row][col]
      ) {
        return false
      }
    }
  }
  return true
}

/**
 * Calculates the probabity for each possible value for every cell
 * @param solutions the list of solutions
 * @returns the percentage probability for each tile of each value
 */
export function calculateProbabilities(solutions?: CellValue[][][]) {
  // All the probabilities are 0 in this case, but we don't know the grid size!
  if (!solutions || solutions.length === 0) {
    return undefined
  }
  // Init our count of each cell value for every tile in the grid to 0
  const probabilities = create2DArray(
    solutions[0].length,
    solutions[0][0].length,
    { 0: 0, 1: 0, 2: 0, 3: 0 }
  )
  for (let row = 0; row < probabilities.length; row++) {
    for (let col = 0; col < probabilities[row].length; col++) {
      // First get the numerator for each cell value probability
      for (let solNum = 0; solNum < solutions.length; solNum++) {
        // Increment the count of solutions with this solution's cell value
        probabilities[row][col][solutions[solNum][row][col]]++
      }
      // Then convert to probabilities by dividing by total count of solutions
      for (const key of Object.keys(probabilities[row][col])) {
        probabilities[row][col][key] =
          (100.0 * probabilities[row][col][key]) / solutions.length
      }
    }
  }
  return probabilities
}

From Solutions to Probabilities

Now we have answered a few of our initial questions: We know whether a puzzle is solvable, and how many solutions it has. But as I’m playing the game, I want to optimize my strategy using the knowledge gained by the solver. One such strategy is to pick all the tiles with the lowest probability of being a Voltorb. To do that, we’ll need the probability a given tile is a Voltorb, which we can get from our solutions simply by counting the number of solutions where the given tile is a Voltorb and dividing by the total number of solutions:

P(tile\ is\ Voltorb) = \frac{\#\ solutions\ where\ tile\ is\ a\ Voltorb}{total\ \#\ of\ solutions}

It’s the same sort of calculation to get a probability of each coin multiplier for a tile. The code is fairly straightforward once we have the list of solutions:

/**
 * Calculates the probabity for each possible value for every cell
 * @param solutions the list of solutions
 * @returns the percentage probability for each tile of each value
 */
export function calculateProbabilities(solutions?: CellValue[][][]) {
  // All the probabilities are 0 in this case, but we don't know the grid size!
  if (!solutions || solutions.length === 0) {
    return undefined
  }
  // Init our count of each cell value for every tile in the grid to 0
  const probabilities = create2DArray(
    solutions[0].length,
    solutions[0][0].length,
    { 0: 0, 1: 0, 2: 0, 3: 0 }
  )
  for (let row = 0; row < probabilities.length; row++) {
    for (let col = 0; col < probabilities[row].length; col++) {
      // First get the numerator for each cell value probability
      for (let solNum = 0; solNum < solutions.length; solNum++) {
        // Increment the count of solutions with this solution's cell value
        probabilities[row][col][solutions[solNum][row][col]]++
      }
      // Then convert to probabilities by dividing by total count of solutions
      for (const key of Object.keys(probabilities[row][col])) {
        probabilities[row][col][key] =
          (100.0 * probabilities[row][col][key]) / solutions.length
      }
    }
  }
  return probabilities
}

While I’m playing, I want to be able to update the probabilities given the tiles I reveal. In other words, as I reveal more tiles, that’s more information that the algorithm can use to narrow down the possible solutions.

All we have to do is filter the list of solutions to the ones where the tile I revealed matches the value of that solution:

/**
 * Filters out solutions that don't match the actual solution
 * @param actualSolution
 * @param potentialSolution
 * @returns true if the values in actualSolution match the potentialSolution
 */
function filterSolution(
  actualSolution: (CellValue | null)[][],
  potentialSolution: CellValue[][]
) {
  for (let row = 0; row < potentialSolution.length; row++) {
    for (let col = 0; col < potentialSolution[row].length; col++) {
      if (
        actualSolution[row][col] !== null &&
        potentialSolution[row][col] !== actualSolution[row][col]
      ) {
        return false
      }
    }
  }
  return true
}

With this filter function, somewhere in your UI you’d do something like:

const filteredSolutions = solutions.filter(solution =>
  filterSolution(actualSolution, solution)
)
const probabilities = calculateProbabilities(filteredSolutions)

where actualSolution is a user reported solution for the puzzle, and solutions is the output of solve().

The Completed Voltorb Flip Probability Tool

Using the code we wrote here, I created some UI for a solver tool for Voltorb Flip. I won’t dive into the code specifics for the UI (maybe I’ll throw something on GitHub), but rest assured this is using our same code for the solver and getting probabilities!

Click on (or tab through) each of the constraints in the following “puzzle” to set them to whatever the in-game constraints are, then click “Solve”.

Then, as you flip tiles within the actual game, click on the tiles in the tool’s grid, enter the value the game revealed, and press the Enter key to see the probabilities adjust to the new information.

Couldn't find solution for the given constraints.

Open up a new window/tab of this post and use the web version at the top to test it out!

Table of Contents