The "Japanese ball puzzle" is a toy I acquired from Motoka Abe and her sons Kuni and Kazu. I fell in love with this puzzle because it was impossible! I spent most spare moments I had during the week I spent with the Abe's (who miraculously put up with our 9 year old sons), trying to get all the colors to line up.
Kazu told me I could take the puzzle home with me. He said he never solved it, so it was clearly a master challenge. I spent the next 2 months twisting the thing and racking my brains, and the closest I got was 21 balls correct and 2 out of order.
I only call this the Japanese Ball Puzzle because I acquired it in Japan. There are no markings on the toy. Many times I thought it must have been manufactured by the devil. I'm sure Kazu would agree!
A huge thank you to Werner Kai who found this page and realized this is the Nintendo Ten Billion Barrel puzzle. Here are the web pages he showed of interest:
http://en.wikipedia.org/wiki/Nintendo_tumbler_puzzle
http://www.jaapsch.net/puzzles/nintendo.htm
The puzzle is cylindrical in shape. It has a plunger which goes up and down on the cylindrical axis. There are 6 rows top to bottom and 5 columns around the cylinder. The plunger only touches 3 columns, so two columns are left alone when the plunger moves.
I call the plunger a toggle in the software. It moves balls parallel to the cylinder axis by filling in one ball position in the top or bottom row. All the balls in the affected columns then push each other up or down. The top and bottom rows do not rotate, and the plunger remains fixed relative to the cylinder.
The inner 4 rows are split into two rings. Each ring holds 2 rows of balls which can be independently rotated around the cylinder. By rotating the cylinders and then toggling, one stores 3 balls in an outer row, and then rotates and toggles back again. The mechanism scrambles the balls around very very fast.
The 3 top holes have 3 black balls to fill them. When the toggle is up, the bottom holes are filled with plungers. The 4 rows in the middle have one color for each column: red, blue, green, orange and yellow. The goal of the puzzle is to get all the colors to line up, with 3 black balls on one side.
The puzzle has 2 rotating cylinders, 3 plunger columns, 5 total columns and 23 balls. That's a lot of prime numbers! One thing that makes this puzzle so difficult is that you can not see all of it at once. It is extremely hard to keep track of what is moving where.
My first attempt at using a computer with the puzzle was to find all the repeat cycles. Doing the same rotations in the same direction caused the balls to come back to the same place. This is similar to the order of a generator in mathematics. While interesting, it did not give me any insight into the structure of the puzzle.
A year later I decided to try a brute force way of solving it. It was a long shot because the total number of combinations is something like:
23!
---------- = 5.41 x 1014
(4!)5 * 3!
and I only wanted to find one of those states!
My first attempt at brute force was simple - rotate the balls around and check for duplicate states, and don't store in memory any repeats. It ran for a full week before I killed it after producing no output. It was obvious that method would not work.
For my second attempt at brute force I decided to be more efficient and not worry about duplicated states. I ended up with several programs the core of which were to follow the twists and toggles of the balls and one to strip out duplicated states. In files of 100,000 states there might be 50 nonduplicated end states. But I got outputs in hours instead of days, so I was happy.
The basic method of following the balls was to use 3 bits to represent each ball color. There were coded from 0 for black to 5 for yellow with red = 1, green = 2, orange = 3 and blue = 4. Since there are 5 balls in each row, I packed one row in a short (16 bit) word. Rotations was then really simple, just mask and move bits. Toggling was a touch more complicated, but I ended up storing 1 bit to represent the toggle up (0) or down (1) and 9 bits to represent the 3 balls on the top or bottom rows. The toggle state bit told me where that one block of bits went.
I then needed to follow the ball motion. In addition to keeping the location of each ball, I kept 25 pointers to all the possible states that particular state could link to. It was a 25 dimensional graph, and the computer (by brute force!) found all the possible links.
Because I used 1 bit in each pointer to mark if the state had been computer or not, I used 23 bits to use as an index into my graph. Each entry point or vertex used 88 bytes with 12 of them used as unsigned ints to hold ball state and 75 of them to hold the 25 pointers to other verticies in the graph. One byte went unused.
I needed the marker because zero index was valid, but many states were not filled. In fact, I could hold 223 states in memory but could only follow about 219 states completely. Given I might have to search some 240 states, things did not seem to good.
The first program ( genstate3.c ) started the whole thing off. I input the ball state with this program and started the search for verticies with 3, 4 or 5 columns. The second program called analstate.c stripped out duplicates and left a pointer file into the results so I could find them easily. The main bulk of the work was done by iterating the program genstate4.c with analstate.c, the first finding as many states as possible, and the second creating a pointer file of non duplicated states.
As the number of states got large, the analstate.c program could no longer handle the output. I then commented out the saving of 3 columns and then continued the process. After several tries, I got the software to work well, and one overnight run left me with a 1.7GB file. This was way too big, so I restarted the run again with the 3 column save commented out. It was not done running when I went to check on the program one morning, but in the middle of the screen it had printed "SOLUTION FOUND". Needless to say, I was more than happy to let the program run its course to finish writing the data out to disk!
I wrote another program called analstate2.c to read in all the files of data and pointers to follow each state from file to file and link them together. A final program printstate.c was used to print out the path so I could easily follow it. I added a search for the shorest path when I found there were 19 paths to the solution, and some were almost 40 steps long while the shortest was 31 steps.
It's clear that simple modifications could be added to these programs, for example adding a flag that tells me at the end of a run if the solution has been found or not. But I'll leave that for another day.
I think I understand why the person who invented this puzzle left no markings on it. Too many people would be upset with them for making such a difficult problem!
