# Algorithm to Solve Puzzle - Advice Needed

Given the following letters arranged in a circular pattern.

    A
B       E
C   D


Each letter can merge with any of its opposite letters to form an adjacent letter. e.g.

A,C => B,B
A,D => E,E

B,E => A,A
B,D => C,C

C,A => B,B
C,E => D,D

D,B => C,C
D,A => E,E

E,B => A,A
E,C => D,D


Now given the following grid of characters:

D A C
B E A
A B E


With the following coordinates:

{0,2} {1,2} {2,2}
{0,1} {1,1} {2,1}
{0,0} {1,0} {2,0}


The aim is to merge adjacent characters until all the characters become A.

Possible solution would be:

1. D{0,2}, A{1,2} = E

E E C
B E A
A B E


2. C{2,2}, A{2,1} = B

E E B
B E B
A B E


3. E{0,2}, B{0,1} => A

A E B
A E B
A B E


4. E{1,2}, B{2,2} => A

A A A
A E B
A B E


5. E{1,1}, B{2,1} => A

A A A
A A A
A B E


6. E{1,0}, B{2,0} => A

A A A
A A A
A A A


I am working on an algorithm that can programmatically solve these types of problems, from 3x3 all the way to 10x10 grids. The number of letters or the rules governing how they merge will not be changed.

I currently have an algorithm which works well but is far from perfect. It is able to solve most puzzles but gets stumped on others, taking either too long to solve or is not able to find a solution at all. Here are the steps with each iteration:

1. Find all instances of the letters C or D. Build a set of moves which will convert C or D into B or E.
1. Score and sort the list of moves based on the following criteria:
• a. Add score for each E have at least 1 adjacent B
• b. Minus score for each E which does not have at least 1 adjacent B and vise versa
1. Select the top move, perform it then repeat until condition in step 4 is met.
1. If all letters are composed of A, or E with 1 matching adjacent B then merge all E with B and complete the puzzle

I am a programmer and game designer, but I have no background at all in algorithms, mathematics or AI. I have approached it from a "What would a smart human player do" point of view.

Any ideas at all would be really be appreciated!

[UPDATE] Improving the heuristics used to score and rank the moves, and also implementing a backtracking search has allowed my current algorithm to solve over 140 levels.

Here's an example of the algorithm working in game:

Performance is still an outstanding problem. The above level took about 2 seconds to solve without any backtracking. Most of the processing time is taken up calculating and sorting all possible moves in each iteration.

• I don't understand. Using the equations, all the numbers have to be equal anyway. (Also, they're all doubled) – boboquack Mar 4 '17 at 10:30
• Sorry if my description is confusing. The equations are not mathematical, they just represent the various combinations of adjacent letters which can be combined. – ImpactBlue Mar 4 '17 at 12:47
• They are mathematical really -- see my answer (which alas doesn't as yet come close to actually answering the question). – Gareth McCaughan Mar 4 '17 at 13:06
• it might help if you used an arrow instead of an equals sign. Perhaps even more so if you used a comma instead of a plus. – Kate Gregory Mar 4 '17 at 16:12

You should think of A..E as 0..4 mod 5. What your rules say is that given any adjacent numbers $x,y$ you can replace them both with $\frac{x+y}{2}$. (2 is invertible mod 5. If it makes you happier you can say $3(x+y)$ instead of $\frac{x+y}{2}$.)
When you do this, the sum of all your numbers-mod-5 doesn't change. So there will be no solution unless the sum equals 0. Suppose the sum is 0. Can you always win? No: if you have a 3x1 rectangle containing $1,1,-2$ then the only thing you can do to change it is to turn it into $1,2,2$, and the only thing you can do to that is to turn it into $-1,-1,2$, and the only thing you can do to that yields $-1,-2,-2$, and the only thing you can do to that yields $1,1,-2$ and you're back where you started.