The game Tricolore XP
A JAVA APPLET (below) demonstrates the solutions of the game.
The remainder of the page discusses the solutions. Cut to the chase.
Putting the diagram above into a letter-based
notation (R = Red, W = White, B = Blue),
Two rows, such as RRRB , BRWR will also be written as RRRB.BRWR
RRRB BRWR WBWR RRBW
If a red square is clicked, it alone advances.
With white, only the adjoining squares advance.
With blue, both it and adjoining squares advance.
you may not click the same square twice in succession.
(This little "wrinkle" gave my programs fits !!)
Press Start to get a new configuration.
Click the colored boxes to play the game.
(Quick rules: R >> W >> B >> R
R: self, W: neighbors, B: self+neighbors
no double clicks - ' x ' = 'forbidden')
Press Solve to see solutions:
for All Red (R), All White (W), or alternating Blue/White (BW).
An optimal sequence of moves is shown and the next box to click has its number shown within.
The upper half is solved first. After it is clicked to completion, the 'action' shifts to the lower half, and the remainder is solved.
Since each square is initially colored independently, there are 316 possible configurations or states of the sixteen squares. By clicking on various squares, you change the configuration.So the questions arise:
These questions are addressed here.
|First, there is only one unreachable configuration, and that one is all squares blue.||
BBBB BBBB BBBB BBBB
1. All blue cannot be reached:
To reach all blue, some square must be clicked last.
If it was blue at the time it changes to red.
If it was white at the time, it stays white.
If it was red at the time, it becomes white.
So no square can be clicked and become or remain blue.
Therefore none of the squares can be clicked last,
and all blue is impossible to reach.
2. All other states can be reached:|
That all other states are reachable was established programmatically, as described below.
I set about programming the problem of transforming configurations to others, but immediately realized that the space was too large to search - at least for my little old PC. So I asked, how could the problem be reduced ?
The first thing that came to mind was approaching it row by row, taking rows in pairs (1-2, 2-3, 3-4) and only clicking on the lower of the two. By restricting clicks to the lower row, previously established rows would not be disturbed.
Two rows have 38 (6561) states, so the total combinations of reaching all states from any state is 316 (43,046,721), a feasible amount. (The same figure for the full 4×4 is 316 squared, or 1.85×1015. Even with elimination of 7/8 of these cases because of symmetry, there would still be a very large number.)
The first two rows could be done without regard to what was happening below and the lower two rows could be solved together. Clicks on the fourth row would affect the third also, but not those above. In most cases, the intermediate stage of doing rows 2-3 can be skipped.
I say "most" because difficulties arise for rows that are all blue: the same argument given above applies to a single row if clicks are limited to it.
I wrote programs to solve the 4×2 problem, starting with the "lower row only" restriction and found that any state other than xxxx.BBBB can be reached.
For the first or third row, there is no problem, because our methods confine clicks to the lower of the two-row pairs. For the second row, we can introduce the intermediate stage, treating it as the top row of a pair. For the bottom row, we have two choices: rotate the board so that the blue rows become blue columns, or, if that introduces new blue rows, use an extension which we describe below.
In the Restricted case (clicking lower row only), any state (other than xxxx.BBBB) is reachable in at most 14-16 clicks. If clicking any of the eight squares is allowed, then, starting from any 4×2 state, any other 4×2 state (except BBBB.BBBB) can be reached in at most 7-10 clicks. This method is called Unrestricted.
I later realized that there is a Hybrid method: restrict clicks to the lower row, but include red squares in the top row, which can be clicked without affecting previous rows. As might be expected, the effectiveness of this method lies between the other two. Its range of maximum required clicks is 10-12.
These numbers are given as ranges because the maximum number of clicks to reach all states varies for different starting states. A scant minority of states (often All Red among them!) require the maximum, as shown below.
For example, with no restrictions, starting from WBWW.WBRW, any other state can be reached in 7 or fewer clicks, whereas from WBWW.WBRB, some 115 states require 8 clicks and just 2 others cannot be reached in fewer than 9!Here are the statistics for all starting states. The table shows how many states were reached at each level, in total, and on average. The range where most paths fall is shown in bold. In gathering statistics, 3321 starting states were considered. Of these, 81 are symmetric about the vertical center. The other 3240 states have mirror images which were not used. (E.g., WWBR.WRRB was discarded because RBWW.BRRW produces the same results.)
So we could solve the 4×4 by first solving the top 4×2 using unlimited clicks and then the bottom 4×2 using only bottom-row+top-red clicks - for most cases. This would result in a total of at most 10+12 = 22 clicks. On average, the number would be 12 or 13, and in about 94% of cases, 16 or fewer.
By rotating the entire board, it is possible to arrange things so that the bottom row is not all blue - unless the desired state has a border of all blue. Then the method of decomposing the 4×4 into two 4×2's has to be extended. Fortunately, the extension is not too, ... well, extensive.
It is as follows:
If the border is all blue, the board looks like this:
B B B B B x x B B x x B (x = any color) B B B B
|Since all-blue is unreachable, at least one of the x-s is not blue. We can rotate the board until the non-blue x is the one lowest and most to the right, indicated here by N:||
B B B B B x x B B x N B (N = 'non-blue') B B B B
|We will make non-blue N our last click. N is either red or white, succeeding blue or white (not red), respectively, with the next-to-last click.|
That means that on the last click, 3 rows will be modified and we
must adjust our target accordingly.
Instead of the target above, we go for:
B B B B B x'x'W B x'N'W B W W W
Then when we click N', we will send it from blue to red or white "to" white, change all the x's and W-s, and reach our desired state, using a total of at most 23 clicks.All the numbers given above are maxima - it would take no more than that many clicks to accomplish a transformation. The vast majority of cases are shorter: for Unrestricted, the average number of clicks required is 5.6, and for Hybrid, it is 7.3.
We can use Unrestricted 4×2 to solve the top two
rows in up to 10 clicks (or 7 in 98% of cases).
Then we can use Hybrid 4×2 (bottom row + top red
clicking only) to solve the bottom half in up to 12 clicks
(or 9 in 96% of cases).
If the desired state has a border of
all blue, then we need one more click, as last
described, to finish.
This method is not quite optimal: we could do better by allowing unrestricted clicking on the whole board. Unfortunately, solving that problem requires more computer (or time) than I have to devote, but this result is pretty close. See Appendix B.
RRRB RRRR BRWR --> RRRR WBWR RRRR RRBW RRRR 17 clicks
|Within a half board, we number the squares as shown here:||
First we do the top half:
The board has gone from:
RRRB RRRR (changed) BRWR --> RRRR (changed) WBWR BRWR (changed *) RRBW RRBW (same)
The first two rows are all red, as desired. The third row has been changed and the fourth row remains as it was.
Then to reach all red, we can do the bottom half: