- #1

DaveC426913

Gold Member

- 19,755

- 3,002

- Summary:
- How complex might the algorithm end up being to solve this colour-matching puzzle in an ideally minimal number of moves?

Just for fun (read as: staring at the ceiling trying to sleep), trying to figure out if there is a programmatic way to solve this colour-matching puzzle app on my phone.

It's called...

Here is a partially solved puzzle:

The dotted tiles are immovable, and serve as references. The undotted tiles can be swapped two at a time.

This is not a

I was idly wondering whether there is a theoretical "perfect" game, by solving it with the minimum possible moves for a given starting configuration with no wasted moves. (Note that every move you make involves the displacement of

A couple steps are involved - some are more engineering that logic - although much of it can be easier done in one's head than with physical automation.

0. Establish conventions:

Columns: A-G, Rows:1-9.

1. Identify the initial configuration.

Capture the colour of tile A1, tag it with its unique RGB value. Repeat 62 times (for this puzzle) all the way to G9.

eg:

[A1:000,000,255], [B1:000,060,255], ...

[A2: 060,000,255], [B2: 060,060,255], ...

... [G9: 255,255,0]

2. Find neighbours.

??

At first I did not see a problem here. I assumed that a neighbour could be identified by subtracting the RG and B values to two tiles. A small reminder means close neighbours. The smallest remainder of all means this

Notice too, that - depending on the difficulty of the puzzle - the difference in tint between neighbours can be arbitrarily small. The whole puzzle might be cool pastels - and that means the RGBs might be so close that neighbours might be arbitrarily hard to distinguish mathematically.

I think there's a lot more logic here than I first thought.

3. Sort.

Use a sorting algorithm that minimizes the number of swaps in the 63-cell dataset. Output a sequence of move instructions.

eg:

[F2 > E2],

[E3 > E9],

[E2 > ??]

I see a problem here too. In step 3, E2 is supposed to move - but its on longer there. It was inadvertently moved in step 1, to make room for F2.

Hope I don't fall asleep too quickly tonight or I'll never figure this out.

It's called...

Here is a partially solved puzzle:

The dotted tiles are immovable, and serve as references. The undotted tiles can be swapped two at a time.

This is not a

*time*challenge; it is a*minimum-move*challenge. i.e.: the fewer moves the better.I was idly wondering whether there is a theoretical "perfect" game, by solving it with the minimum possible moves for a given starting configuration with no wasted moves. (Note that every move you make involves the displacement of

**two**tiles, but normally only**one**is put in its final location).A couple steps are involved - some are more engineering that logic - although much of it can be easier done in one's head than with physical automation.

0. Establish conventions:

Columns: A-G, Rows:1-9.

1. Identify the initial configuration.

Capture the colour of tile A1, tag it with its unique RGB value. Repeat 62 times (for this puzzle) all the way to G9.

eg:

[A1:000,000,255], [B1:000,060,255], ...

[A2: 060,000,255], [B2: 060,060,255], ...

... [G9: 255,255,0]

2. Find neighbours.

??

At first I did not see a problem here. I assumed that a neighbour could be identified by subtracting the RG and B values to two tiles. A small reminder means close neighbours. The smallest remainder of all means this

**is**a neighbor. But it doesn't yet tell us*which*neighbour it is. It could be one of four.Notice too, that - depending on the difficulty of the puzzle - the difference in tint between neighbours can be arbitrarily small. The whole puzzle might be cool pastels - and that means the RGBs might be so close that neighbours might be arbitrarily hard to distinguish mathematically.

I think there's a lot more logic here than I first thought.

3. Sort.

Use a sorting algorithm that minimizes the number of swaps in the 63-cell dataset. Output a sequence of move instructions.

eg:

[F2 > E2],

[E3 > E9],

[E2 > ??]

I see a problem here too. In step 3, E2 is supposed to move - but its on longer there. It was inadvertently moved in step 1, to make room for F2.

Hope I don't fall asleep too quickly tonight or I'll never figure this out.