Solving a puzzle using search algorithms

Question

I came across a puzzle a few days ago. It's solvable easily by hand. But I was trying to build an algorithm for solving it. But i dont know how I should proceed.

Here you can see that i have to connect all pairs of colored dots. For example i need to connect yellow dot to another yellow dot, green to other green, blue to blue and so on.

Here is an example of how it should be solved. if the description was not clear.

So you can see that i connected yellow dot with another yellow dot. And blue with another blue. But this causes a problem. I've blocked the path of aqua color as you can see. I hope you get the idea.

So i want to solve it. Brute force approach would work but it will take a long time and i'm not interested in that. I tried about implementing Breadth First Search, Depth First Search, and Dijkstra algorithm. But i think they won't be good in this case. Correct me please if I'm wrong. A* Search may work, but what will be the heuristic?

Can anyone give me some intuition on how to solve the problem?

Answer 1

I genetic algorithm might be an appropriate means to get a solution. The fitness function and the cross-over would have to be tailored specifically for the problem.

Chromosome:

• 9x9 2d array of ints (genes)
• Your 18 unique colored peices will be statically set as 512|1, 512|2, 512|4, 512|8, 512|16, 512|32, 512|64, 512|128, 512|256 representing the 9 unique colors; 512 (2^9) will be the flag denoting them as static/unchangable genes.
• Colored connecting squares will have 2^0-2^8 values, these genes can change and be composed, a value of 3 (011b) would mean 2 colors (1 and 2) are sharing the same square.

Fitness function off the top of my head

• Spaces with 1 unique color are +8, 2 colors +6, 3 colors +4, 4 colors +2, 5 colors +0, 6 colors -2, 7 colors -4, 8 colors -6, all 9 colors -8
• Spaces connected (left,right,up,down) with a matching colored static space are +9
• Spaces connected with a matching colored space in 1 direction +4, 2 directions +3, 3 directions +2, 4 directions +1

Mutation

• Logical XOR a random color bit (1 << Floor(Random() * 9)) with a random non-static gene

Cross-Over / Breeding Off the top of my head

• Copy your 2 candidate chromosomes
• Clear out genes within the copies that contain 5 or more overlapping colors
• Logical OR the two chromosomes together to get your result