Think-a-Dot has an upright frame with three openings at the top, into which you can drop a marble. The marble travels through and drops out the bottom. There are eight dots on the front of the frame, in rows of three, two, and three, and they are yellow or blue. They indicate the state of a flip-flop gate inside the frame. If a marble reaches a gate, it is deflected either left or right depending on the state of the gate, and as the marble passes, the gate will flip over to the other state.
At the start you tilt the frame to the right (or left), so that all the gates face the same way. The four corner gates are coloured differently than the rest, so the corner dots will be yellow, and the rest blue (or vice versa if you tilted it to the left). Given a particular target pattern of dots, the aim is to drop the marble into the holes at the top until the target pattern is reached, preferably in as few moves as possible.
This puzzle was made by E.S.R. Inc. in around 1966. Its patent, US 3,388,483, was filed by Joseph A. Weisbecker in July 21, 1966, and granted June 18, 1968. The letters E.S.R. stand for Education Science Research (not Edmund Scientific as is sometimes thought) and they made several fascinating contraptions:
|Name||Patent, filing date||Description|
|Digi-Comp 1||US 3,273,794, Oct 21 1963||A mechanical model of a 3-bit computer, using sliding plates, programmable by attaching rods to make parts interact.|
|Digi-Comp 2||US 3,390,471, Apr 30 1965||A mechanical model that does binary arithmetic (add, subtract, multiply, divide, complement and negate), using marbles and flip-flop gates. It looks like a pinball machine.|
|Dr. Nim||Also US 3,390,471||A mechanical Nim playing machine, using 15 marbles and three flip-flop gates.|
|Think-a-Dot||US 3,388,483, Jul 21 1966||A mechanical puzzle, using one marble and 8 flip-flop gates.|
Much of what follows below is based on the texts on the Fractions-plus site (now to be found at docstoc).
I will label the three openings at the top A, B, and C.
Every move changes the state of some gates, which in turn changes what the next move will do. You would therefore initially expect the order in which you do moves to matter. The amazing thing is however that it doesn't. So A followed by B is the same as B and then A. Similarly B C is the same as C B. The reason for this is clear if you imagine the two moves being done simultaneously. If the marbles are at different gates in some row, then their order is obviously unimportant because those two gates are independent of each other. If at some row the two marbles have to go through the same gate, then again it doesn't matter which marble goes through first, as the marbles are identical. One marble will be deflected one way, the second the other way, but it doesn't matter which is which. Their combined effects are the same regardless of the ordering.
The move order is immaterial, so lets simply represent them by three numbers, the number of marbles that are dropped into each column. A triple (a,b,c) means that a marbles are dropped in column A, b in column B, and c in column C.
If we drop two marbles in a column, the first row will be unaffected. This is because the second marble undoes the first row flip that the first marble did. Those two marbles will, however, take different paths when passing through the remaining rows and so have different effects there. If we drop another two marbles in the same column, the first row is unaffected still, but now they undo the effect the first two marbles had on the second row. If we now double the number of marbles again, putting a total of 8 marbles in the same column, then even the third row will be unaffected. This shows straight away that you need never put eight or more marbles in any one column, and the worst case certainly won't need more than 7+7+7=21 moves. As we shall see later, the worst case is actually 9 moves.
The previous paragraph suggests that we can solve the puzzle row by row, first solving the top row with single moves, then the second row with double moves, and finally the last row with quadruple moves. We simply have to find out how the double moves (2,0,0), (0,2,0), and (0,0,2) affect the middle row, and how quadruple moves affect the last row. This leads to this strategy:
This method is quite efficient, taking at most 9 moves. There are in fact some positions that cannot possibly be solved in fewer, so in those cases this method is optimal. It is however not optimal for all positions, as there are some that can be solved in fewer moves than this method uses.
There is another way to see that repeating a move 8 times will have no effect. Take a look at any three gates that a single marble might go through if you put it in column B. For example, take the diagonal from column B to the left of the bottom row. The state of some of those three gates changes by dropping the marble into column B. If you try it out you will see that the three gates change the same way as a three-bit binary counter does, counting from 000 to 111, and then wrapping back to 000. A gate represents a 1 if it would let the marble through to the next gate in the path, and a 0 otherwise. The three gates will therefore be back to their initial state after 8 moves. This actually holds for any such path of three gates (even for the path along all the leftmost gates, or the one along all the rightmost gates, which behave slightly differently), so after 8 identical moves everything will be back to the initial state. This suggests the following very simple solution:
In the above method the worst case is (1,7,7) which has 15 moves. This is clearly not as efficient as the first method, but it is easier to remember.
Consider the moves (2,2,2). If you imagine 6 marbles dropping at the same time, two in each column, then you will see that the first row of dots will obviously not change, but neither will the second row because each gate gets two marbles, one arriving from the left and one from the right. The same goes for the last row, it also does not change. So regardless of the current state of the dots/gates, the moves (2,2,2) will have no effect.
We can use (2,2,2) to create better solutions. Suppose we found that the moves
(3,2,6) created the pattern we want. If we apply (2,2,2) to it we still have the
same pattern, but we have done (5,4,8) all together. We know that 8 times the same
move has no effect either, so this is the same as (5,4,0). So the pattern we got by
doing the 11 moves (3,2,6) can also be created by the 9 moves (5,4,0). We can apply
(2,2,2) again to get (7,6,2), and again to get (9,8,4) = (1,0,4),
and once more to get back to (3,2,6) which is where we started.
We now have four alternative solutions (3,2,6), (5,4,0), (7,6,2), (1,0,4), of which the last one is the best with only 5 moves.
Given any triple (a,b,c) with a,b,c<8, we get four triples that have the same effect - the triple itself, and three more by adding (2,2,2) one, two or three times. There are 83 triples, so these form 83/4 = 128 sets of equivalent triples. As there are also 128 reachable positions, such a set forms a complete set of solutions for a position. If we therefore have one solution for a pattern we can generate the set of four solutions, and if we then choose the best of those it will certainly be the optimal solution to that pattern.
An optimal triple will have the following properties:
The largest number of an optimal triple is at most 5, the medium largest at most 3, and the smallest at most 1. So an optimal triple will never have more than 1+3+5=9 moves. Furthermore, triples such as (1,3,5) are actually optimal, so the worst case positions of Think-a-Dot have 9 moves.
It would be nice to be able to look at a dot pattern and be able to figure out an optimal solution without doing any moves before hand. Neither of the previous solution methods are suitable, since they have decisions based on the state of the dots after some moves have already been done. To eliminate this, we can use a variation of the second method.
Where this method scores above method 2 is that steps b and c are independent. The state of the leftmost dots is not affected by C moves, and the state of the rightmost dots is not affected by A moves. You only have to be able to look ahead at most one move - once you know the dot pattern after step a, you can deduce the number of marbles needed in columns A and C. In fact, even this amount of look ahead is not necessary. Using binary arithmetic, we can calculate everything.
Suppose the current position has blue dots at the top left and top right, and the other 6 dots are yellow. Suppose that our target pattern has yellow dots at the top left and bottom left and blue dots everywhere else.