Study of Tricolore XP

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 3¹⁶ 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 ?

These questions are addressed here.

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 3⁸ (6561) states, so the total combinations of reaching all states from any state is 3¹⁶ (43,046,721), a feasible amount. (The same figure for the full 4×4 is 3¹⁶ squared, or 1.85×10¹⁵. 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.

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	Average	Percent
1	25092	7.6	0%
2	126341	38.0	1%
3	608623	183.3	3%
4	2440042	734.7	11%
5	6550422	1972.4	30%
6	8140823	2451.3	37%
7	3376269	1016.6	16%
8	495642	149.2	2%
9	22418	6.8	0%
10	88	0.0	0%
11	--	--	--
12	--	--	--
Total	21785760	6560	100%
Average Clicks		5.6	94%

**Hybrid**
Clicks	Reached	Average	Percent
1	17652	5.3	0%
2	55834	16.8	0%
3	182285	54.9	1%
4	536865	161.7	3%
5	1483846	446.8	7%
6	3440533	1036.0	16%
7	5804350	1747.8	27%
8	5853716	1762.6	27%
9	3192766	961.4	15%
10	871813	262.5	4%
11	79094	23.8	0%
12	1326	0.4	0%
Total	21520080	6480	100%
Average Clicks		7.3	85%

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.

Method	Final State	Average	Maximum
Unrestr. 4×2	`WWWW.WWWW`	4.6	6
	`WBWB.BWBW`	5.0	7
	`RRRR.RRRR`	7.4	10
Hybrid 4×2	`WWWW.WWWW`	5.6	9
	`WBWB.BWBW`	6.3	9
	`RRRR.RRRR`	8.7	12

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:

Clicks	State	Click here
`init`	`RRRB.BRWR`	`(4)`
`1`	`WWRB.RWWR`	`0`
`2`	`WBRB.WBWR`	`1`
`3`	`BRWB.BRBR`	`2`
`4`	`BWWR.BWRW`	`3`
`5`	`BWWW.BWRW`	`2`
`6`	`BBWB.BBWB`	`3`
`7`	`BBBR.BBBR`	`1`
`8`	`RRRR.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:

Clicks	State	Click here
	`BRWR.RRBW`	`(3)`
`9`	`BRWW.RRBW`	`6`
`10`	`BWBB.RWRB`	`5`
`11`	`RBRB.WWWB`	`(0)`
`12`	`WBRB.WWWB`	`(2)`
`13`	`WBWB.WWWB`	`5`
`14`	`BRBB.BWBB`	`(1)`
`15`	`BWBB.BWBB`	`4`
`16`	`RBBB.RBBB`	`6`
`17`	`RRRR.RRRR`	`done`
( ) : top (third) row - must be red

(Squares are numbered relative to two-row board.)

Appendix B: The Programs

See Index2.html

Thank you.