Algorithm to Solve Puzzle - Advice Needed

Question

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.
• 2. 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
• 3. Select the top move, perform it then repeat until condition in step 4 is met.
• 4. 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.

Answer 1

Very partial answer

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.

I have a suspicion that (1) this is essentially the only situation in which you can't win despite the sum being 0 and (2) when you can win you can always win "one-dimensionally" (construct a path covering the whole array; e.g., left to right along the top row, then right to left along the next, then left to right along the next, etc., and then only ever apply your operations "along" this path).

[EDITED to add:] As Peter Taylor rightly points out in comments, the above definitely isn't the only zero-sum situation where you can't win: if, say, you have a 5x5 rectangle containing only 1s then there's nothing you can do.