Voltorb Flip – Optimizations

The Simple Optimization
The simplest optimization to explain is as follows: because empty tiles are filled in order when solving the board, I don’t have to recheck all the ones that have already been solved. Basically, I just save the row and column every time I recurse into the solve function, so it starts at the last tile solved, rather than looking through the beginning.

The “Move” Optimization
My original method essentially said:

1. Solve the board
2. Get the user’s move, and store it in the board
3. Go to step 1

This was time-consuming, and I soon realized that there was a nice alternative: rather than re-solving the board, I could simply go through the previous listed of solutions from before, and remove the ones that didn’t include the move the user entered. This came with problems, however. First of all, you should know that there are three main ways to store a list of solutions inside a program:

1. Using a vector; vectors allow for constant-time random-access, and linear-time removal/insertion at any place but the end
2. Using a list; lists allow for linear-time random-access, but constant-time removal/insertion
3. Using a deque, which is similar in efficiency to a vector

Now, solving a board is technically exponential time, so any of those options is better, but I wanted the best one. I then remembered a beautiful little trick wowus showed me, which was that, when removing from an unsorted vector, you can do it in constant time by swapping the element you want to remove with the last element, and then removing the last element (which can be done in constant time). Voila! I implemented this, and now the whole simplification runs in linear time, as does random access. I realized later that I never actually access randomly, but only iterate, so a list could have done just as well as a vector. Oh well.

The Solver Optimization
This is a hugely important optimization, despite the fact that it’s very few lines of code. First of all, realize that in a 25-tile board, where each tile can be 4 possible things, there are 4^25 permutations. Now, if we try each one, and then try to check if each one is valid, this would take an unfathomable amount of time (4^25 is like the number of characters you could store in .TXT files in a 1,000,000 GB hard drive).

What can be done, however, is after a tile is modified, no matter which tile it is, recheck the row and column that tile was in. If the row/column is no longer valid, we don’t need to try and solve the rest of the board (none of the solutions will be valid, because they contain some impossible row/column), we can simply move on to the next step without recursing.

Now, how does one check if a row/column is valid? It’s actually quite easy. First of all, we check if the sum of all the tiles in the row/column exceeds the sum the board tells us for that row/column; if it’s too big, it’s invalid. Next, we check if the number of voltorbs exceeds the number the board tells us for that row/column; if it’s too big, it’s invalid.

Now it gets a little trickier. We take the number of unknown tiles left in the row/column, and we subtract the number of voltorbs we have yet to find in that row/column. That gives us the number of tiles that actually have values. We multiply the number of valuable tiles by 3 (the maximum possible value), and add it to whatever sum we already have for that row/column. If it’s less than the sum the board tells us for that row/column, it’s invalid. In other words, this just assumes the rest of the tiles are all 3s, so if you can’t hit the required sum with all 3s, then there’s no way it can be valid.

I lied a little on the Solver blog post; it's not quite as simple as what I wrote; there's that extra validation step every time you change a tile.