A Study of Tricolore XP       Home

The game Tricolore XP (Creator's version) is studied.
A JAVA APPLET (below) demonstrates the solutions of the game.
The remainder of the page discusses the solutions. Cut to the chase.

### The Game

Tricolore XP consists of a 4×4 array of squares, each occupied by a color: Red, White, or Blue, and rules governing the changes to those colors.

 Putting the diagram above into a letter-based notation (R = Red, W = White, B = Blue), we get: ``` Two rows, such as RRRB , BRWR will also be written as RRRB.BRWR ``` ``` RRRB BRWR WBWR RRBW ```

### The rules

The goal is to reach a predetermined state, such as all squares the same color.
(White: easy, Red: difficult, Blue: read on ...)

When a square is clicked, colors advance, according to the sequence
Red >> White >> Blue >> Red ...
 If a red square is clicked, it alone advances. With white, only the adjoining squares advance. With blue, both it and adjoining squares advance. IMPORTANT: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.

### The Study

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:
• what configurations are possible ?
That is, starting from one state, what other states can be reached via a sequence of clicks ?
• And, to reach some other state, what is the shortest sequence of clicks that will do so ?

#### What can be reached ?

 First, there is only one unreachable configuration, and that one is all squares blue. ``` BBBB BBBB BBBB BBBB ``` Proof: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.

That's not too bad, one impossible state out of 43 million plus.

#### How many states ?

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.)

#### Reaching the others

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.

##### More problems with blue

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.

#### A better way

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.

##### Why the ranges ?

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.)

Unrestricted
Clicks Reached AveragePercent
1 25092 7.60%
2 126341 38.01%
3 608623 183.33%
4 2440042 734.711%
5 6550422 1972.430%
6 8140823 2451.337%
7 3376269 1016.616%
8 495642 149.22%
9 22418 6.80%
10 88 0.00%
11 -- ----
12 -- ----
Total 217857606560100%
Average Clicks5.694%

Hybrid
Clicks Reached AveragePercent
1 17652 5.30%
2 55834 16.80%
3 182285 54.91%
4 536865 161.73%
5 1483846 446.87%
6 3440533 1036.016%
7 5804350 1747.827%
8 5853716 1762.627%
9 3192766 961.415%
10 871813 262.54%
11 79094 23.80%
12 1326 0.40%
Total 215200806480100%
Average Clicks7.385%

Unrestricted has more total states because it can reach the 80 xxxx.BBBB states which the other cannot.

The following data is reversed: showing numbers of clicks to reach a few selected final states, compiled over all possible starting states.

MethodFinal StateAverageMaximum
Unrestr. 4×2WWWW.WWWW4.66
WBWB.BWBW5.07
RRRR.RRRR7.410
Hybrid 4×2WWWW.WWWW5.69
WBWB.BWBW6.39
RRRR.RRRR8.712

We see that All White (WWWW.WWWW) is relatively easy, the Alternating pattern (WBWB.BWBW) falls in the middle, and All Red (RRRR.RRRR) is the most difficult of the three. (Typically, All Red is one of the most difficult of all.)

The table also shows that there is a shorter path from All Red to All White than clicking each red square. That would take 8 clicks and the maximum from any state is 6 - in fact, there is a sequence of 4 clicks !

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.

#### Still too much blue ?

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 ```
Where x' and N' denote predecessors of x and N, and W can be thought of as B'. This can be achieved using the method above with no more than 22 clicks.

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.

### In summation

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.

Overall, in 94% of cases, 16 or fewer clicks are needed, on average, 12.9.

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.

#### Appendix A: An example

A typical goal is a board of all one color. We know that all blue is impossible. All white can usually be reached quite quickly (eliminate blue, click on red), but all red is a bit more difficult, since the predecessor of red is the always pesky blue.
```        RRRB           RRRR
BRWR    -->    RRRR
WBWR           RRRR
RRBW           RRRR
17 clicks
```
Within a half board, we number the squares as shown here:
```  0123
4567
```
First we do the top half:

initRRRB.BRWR(4)
1WWRB.RWWR0
2WBRB.WBWR1
3BRWB.BRBR2
4BWWR.BWRW3
5BWWW.BWRW2
6BBWB.BBWB3
7BBBR.BBBR1
8RRRR.RRRR
( ) : affects third row
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:
BRWR.RRBW(3)
9BRWW.RRBW6
10BWBB.RWRB5
11RBRB.WWWB(0)
12WBRB.WWWB(2)
13WBWB.WWWB5
14BRBB.BWBB(1)
15BWBB.BWBB4
16RBBB.RBBB6
17RRRR.RRRRdone
( ) : top (third) row - must be red
(Squares are numbered relative to two-row board.)

See Index2.html

Thank you.