Few people perhaps realize that Nintendo® have been around for a very long time. The company was originally founded back in 1889 in Kyoto, Japan and manufactured playing cards for decades before trying more diverse business ventures in the 1960’s. Nintendo experimented with taxi services, a chain of “love hotels”, instant rice and a TV network; all failed. They were more successful with moves into the toy industry in 1966, including some early electronic games – but Game and Watch in 1980, and Donkey Kong in 1981, saw the company become the video game giant it is known as today. Long-time Nintendo employee Gunpei Yokoi was the creator of Game and Watch, and the highly successful Game Boy, and invented the ubiquitous “D-pad” direction controller. In his spare time, Yokoi also invented the Ten Billion Barrel puzzle. It is one of the most difficult puzzles of its kind. With the aid of a computer algebra system, can an efficient solution be found?
What is Ten Billion?
Thirty years ago, the world was still in the grip of the mania about Rubik’s Cube, and as a young teenager I was no exception. I hungrily collected as many “magic puzzles” as I could, getting several as birthday and Christmas gifts. After the Rubik’s Cube, many of these puzzles seemed derivative; many of them were fairly easy to solve, particularly with the knowledge that many move sequences and ideas in cube solutions could be used for the other puzzles. The Ten Billion barrel puzzle proved very different indeed. It is exceptionally difficult, because every move disturbs no less than 10 of the 23 pieces. I could not come up with any ideas on how to complete it; the best I could do was three of the five colors. Published solution methods take long chains of moves and are hard to commit to memory.
The Ten Billion barrel puzzle is an ingenious design, consisting of a cylinder with five grooves, each containing four balls of one of five colors. The top and bottom halves of the cylinder can rotate independently; but all is not as easy as it seems. Three of the five columns are actually five balls long, with an extra black ball at the end, and a plunger can push the balls in those three columns one place up or down. The result is a fiendish puzzle that can arrange the balls in – guess how many permutations? The number isn’t what you expect. Even if the five main colors are interchangeable, the puzzle has a remarkable four and a half trillion distinct positions – far more than that “ten billion” figure. Recently Nintendo released a special “Mario star” edition for Club Nintendo members.
My original Ten Billion puzzle is likely in my parents’ attic eight thousand miles away, so last year I picked up another on eBay, determined that this time I would find a solution method of my own, using all that combinatorics, permutations, and group theory I studied for my math degree. For many simpler puzzles, one can calculate a “god algorithm“, by literally creating all the knowledge of an omniscient being about the problem. For every unique position of the puzzle, a table or computer program delivers the optimal move for the quickest solution. I guessed for the Ten Billion puzzle, such a method would need petabytes of storage and millions of hours of computation. (I am happy to say it needed far less after all!) “Human” solutions tend to solve one row or one column at a time. A mathematical method however could perhaps look at the entire configuration at once. This is the approach used by Morwen Thistlethwaite in his renown 52-move algorithm to solve the Rubik’s Cube, which laid the foundations for many constructions of even shorter results. Perhaps a similar approach can apply for the Ten Billion puzzle, reducing the problem into stages which are reasonably computable?
To aid in this effort, I installed the GAP System for computational discrete algebra, and in within an hour of my first interactive session, I replicated some results previously reported by David Singmaster; namely, that all even permutations of the 23 pieces were achievable, even with the two barrels locked together, and the odd permutations are possible by flipping the puzzle over. Furthermore, a similar result holds true considering just one barrel and the 13 balls it can manipulate with the plunger up or down. After some more consideration (and several overnight calculations), I came up with the solution outlined below, that solves any configuration of the Ten Billion barrel puzzle in 38 moves or fewer.
The Ten Billion Solution Within 38 Moves
The basic approach is to split the puzzle into three stages. The first stage moves balls into the correct half of the puzzle; broadly speaking, two of each main color in each barrel, and all the black balls at the top. (In fact, not all the balls need be in the correct half at this stage). Then in the remaining stages, the method solves each half using only moves of one of the barrels, leaving the other ten balls undisturbed. Each of these stages is well within the scope of a god algorithm. For convenience, the solution uses the same labeling and notation scheme as at Jaap’s Puzzle Page for the Nintendo Ten Billion Barrel.
The first stage is to moves all the black balls, and at least one ball of every main color, into the top barrel. This can often be done intuitively, but for the purpose of this proof, an exhaustive search found short move sequences that take one particular ball from the 10 in the bottom barrel, and move it to the top section, while bringing one of the 13 balls in the top down to the bottom. (The positions of the other balls may of course change but do not matter at this point). The longest of these 130 such sequences take eight moves, but these long sequences are in fact not needed; there is always another, shorter choice. A brief calculation shows this needs no more than three flip move sequences, in a total of 12 moves or fewer.
Stage 2 solves 10 balls in the top half of the puzzle using top barrel rotations only. It turns out that there are “only” 3,603,600 arrangements of the top 13 balls after stage 1, taking into account the symmetries of switching colors or pairs of same-colored balls. The god algorithm for these positions is certainly computable, and solves the top half in at most 13 moves. In the example, the method selects orange and yellow for columns B and D. The move sequence trr Tl tr Tr tll Tl tr Tl trr Tr tl solves all the black balls, all of row 4, and orange and yellow balls in the correct positions on row 3.
The last stage is yet another lookup in a god algorithm table, and proceeds in much the same way as stage 2, solving the remaining balls with bottom barrel rotations only. This time, however, there is no choice of colors; stage 2 fixed the colors of each column. There is still an arbitrary assignment of ball positions within each column, so the god algorithm can use that symmetry. There are 7,207,200 possible permutations for this stage. This produces a move sequence that solves all the remaining balls within 13 moves. The example has decided to order the colors green, yellow, red, orange, blue, and solves all the remaining balls with Brr bll Bl brr Bl brr Bll bl. This example took far fewer moves than 38.
Putting it All Together
By adding up the lengths of the individual stages, the solution method can solve any configuration of the Ten Billion barrel puzzle in 38 moves or fewer – and it is certain that there are improvements. However, I believe this is the first result of its kind for the Ten Billion puzzle. To enable further research, checking of my results, running the solver, and hopefully improving it, I am publishing all the GAP code and the god algorithm database dumps for stage 2 and stage 3 under this site’s Creative Commons license (thanks to Dropbox for hosting them).
- GAP code (zip archive, 17 KB)
- Stage 2 god algorithm data (zip archive, 25.9 MB)
- Stage 3 god algorithm data (zip archive, 53.2 MB)
You will need the GAP software installed on your system and unzip all the files into one directory. Be warned, the unzipped god algorithm files are very large and will need about 550 megabytes of disk space! (These files allow the solver program to run without a database). They may also take several minutes for the solver program to load, so have patience. If you do install the solver, you can create or edit a file like example.g, and use GAP to solve it by:
gap> Read("example.g"); gap> Read("solver.g");
Wait a while, and the solution will appear! The distribution also includes all the code and database definitions used to do all the computations, including the god algorithms themselves. With some edits, you may use this to calculate tables for your improved solution; these are purely historical results now, since a far better solution soon followed…
The Final Solution in 18 Moves
(Updated). Some intrepid investigators did indeed take up the challenge to search for better results, and implemented some very efficient code to do so. You may read more details about the search in the Domain Of The Cube forum, a hangout for both mathematicians and enthusiasts of the Rubik’s Cube and other similar puzzles. Tom Rokicki, a member of the team that proved God’s Number is 20, immediately went to work and wrote an efficient program to solve any barrel position in as few moves as possible; and after testing millions of positions, surprised me: the hardest he had found took a mere 17 moves. After some more searching, a handful of positions were found at depth 18. While not a proof, the evidence suggested that 18 was probably the limit.
With some more advanced coding of a program called a “coset solver” (and some good computer hardware), Tom proceeded to split the search into 1771 smaller searches, each of about 2.5 billion positions. Because of mirror symmetries, only 467 of the searches needed to run. The results began to creep in (which Bruce Mackenzie and myself helped to verify). First Tom demonstrated that 10 moves are enough to get all the black balls to the top, then the puzzle solved in at most 16 more. My bound of 38 dropped to 26. As more results came in, the number reduced further, to 23, then to 19. Finally, on November 13 2013, Tom announced all 467 searches had completed. All positions of the Nintendo Ten Billion Barrel puzzle can be solved in 18 moves or fewer. A mere 28,564 positions take 18 moves exactly. Congratulations to Tom on this impressive calculation!