2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't understand. Using the equations, all the numbers have to be equal anyway. (Also, they're all doubled) $\endgroup$ – boboquack Mar 4 '17 at 10:30
  • $\begingroup$ Sorry if my description is confusing. The equations are not mathematical, they just represent the various combinations of adjacent letters which can be combined. $\endgroup$ – ImpactBlue Mar 4 '17 at 12:47
  • $\begingroup$ They are mathematical really -- see my answer (which alas doesn't as yet come close to actually answering the question). $\endgroup$ – Gareth McCaughan Mar 4 '17 at 13:06
  • 1
    $\begingroup$ 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. $\endgroup$ – Kate Gregory Mar 4 '17 at 16:12
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There's also the case where the sum is zero (mod 5) but all the numbers are equal and you can't change anything. $\endgroup$ – Peter Taylor Mar 4 '17 at 23:05
  • $\begingroup$ Good catch! I missed that. $\endgroup$ – Gareth McCaughan Mar 4 '17 at 23:43
  • $\begingroup$ Hey @GarethMcCaughan the rule actually only allows numbers which are at least 2 apart to be merged. So the combinations would be: 0,2 => 1 1,3 => 2 2,4 => 3 3,0 => 4 4,1 => 0 The puzzles are built by working backwards from a finished state, so they will always be solvable at the start. However it is possible for the player to transition to an unsolvable state based on the moves made. Being able to calculate if the current state is unsolvable would be really useful for culling failed branches. $\endgroup$ – ImpactBlue Mar 5 '17 at 7:19
  • $\begingroup$ Oh, I completely failed to notice that too. Bah, silly me. Sorry about that. It seems like this restriction will complicate the analysis a lot... $\endgroup$ – Gareth McCaughan Mar 5 '17 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.