How to evaluate all possible groups of adjacent tiles in 2D array?

Question

I'm working on a tile based game idea in Javascript. It's a math puzzle game where players move around tiles with numbers on them, and the goal is to connect groups of tiles that have a sum of certain goal number, for example 5 or 7 or 9. However, I'm stuck on the algorithm to detect these sum groups. I know how to do a flood fill algorithm using recursion to detect a group of adjacent tiles, like in the same game. But I don't know how to iterate through all the possible permutations of possible groups, and what is the best way to approach this?

Because the problem is that adjacent tiles form a group, but within that group of tiles there are many possibilities for sub groups. See tiles example below

Tile letters     Contains numbers    Represented as graph
+---+---+---+    +---+---+---+
| A | B | C |    | 1 | 5 | 2 |       1---5---2
+---+---+---+    +---+---+---+       |   |
| D | E | . |    | 2 | 1 | . |       2---1
+---+---+---+    +---+---+---+       |
| F | . | . |    | 4 | . | . |       4
+---+---+---+    +---+---+---+

So the group is all the tiles A though F, and a subgroup could be A, B and E (1+5+1) but also A, D and F (1+2+4). But A, C and F is not a possible group because those tiles are not adjacent. I suspect it could maybe be approached like it's a graph problem. But then I still don't know how to handle the many possible circular nodes.

So my question is; How to systematically go through and evaluate all possible permutations? Is there an algorithm for something like this? Or can someone explain how to approach this problem?

EDIT: I've put my code in the jsfiddle in the link below. It uses flood fill from a starting tile, in the example tile with nr 2. Then for each cell it counts to 15 and uses the bits of that counter to flood-fill to the 4 adjacent tiles (up,down,left,right). However it doesn't work properly because it doesn't consider branching paths. For example, in the jsfiddle example the combination 3-2-4 is never evaluated. https://jsfiddle.net/wu6p49r2/

I know how to do it by hand, see examples below. But what would the algorithm look like, to systematically gather these possible adjacent combinations starting at A?

Tiles ex.1    Tiles ex.2        Tiles ex.3
+---+---+     +---+---+---+     +---+---+---+
| A | B |     | A | B | C |     | A | B | C |
+---+---+     +---+---+---+     +---+---+---+
| D |         | D | E |         | D | E |
+---+         +---+---+         +---+---+
                                | F |
                                +---+
All possible adjacent combinations,
starting at A:

A             A                 A
A-B           A-B               A-B
A-D           A-B-C             A-B-C
A-B-D         A-B-E             A-B-E
              A-B-C-E           A-B-C-E
              A-B-E-D           A-B-E-D
              A-B-C-E-D         A-B-C-E-D 
              A-D               A-B-E-D-F
              A-D-E             A-B-C-E-D-F
                                A-D
                                A-D-E
                                A-D-F
                                A-D-E-F

Answer 1

Your groups of tiles can be considered as graphs, where vertices represent tiles and two vertices are connected by edge if and only if their corresponding tiles touch each other side by side. So, in terms of graph theory, the problem you are trying to solve is known as CISE (Connected Induced Subgraphs Enumerating). You can find a number of papers, describing algorithms to solve this problem - I'll excerpt here some results from this paper.

We consider undirected simple graphs $G = (V,E)$. Some notations:

• For any vertex $v \in V$, the open neighborhood of $v$ is defined as $N(v) = \{u \space | \space {u, v} \in E\}$ and the closed neighborhood of $v$ is defined as $N[v] = N(v) \cup \{v\}$.

• For any vertex set $W \subseteq V$ the open neighborhood of $W$ is defined as $N(W) = \bigcup_{v∈W} N(v) \setminus W$ and the closed neighborhood of $W$ is defined as $N[W] = N(W) \cup W$.

• The graph $G[W]$, induced by a vertex set $W \subseteq V$, consists of all edges from $E$ with both ends in the $W$, so $G[W] = (W, \{\{u,v\} \in E \space | \space u,v \in W\})$.

The following recursive function will list all the connected induced subgraphs of the graph $G$, starting from some vertex. Both arguments $P$ and $X$ of this function are vertex sets. The function call Enumerate({v}, N(v)) will list all the connected induced subgraphs, starting from some vertex $v \in V$. All these subgraphs will contain this vertex. Operations + and - denote set operations union and minus on vertex sets.

Enumerate(P, X)
  output P
  while vertex set X is not empty
    u = any vertex from X
    remove u from X
    X' = X + (N(u) - N[P])
    Enumerate(P + {u}, X')

In order to list all the subgraphs, not including this vertex $v \in V$, it should be removed from the graph $G$, and then the above recursive function should be called with another starting vertex.

I've implemented this algorithm and tested it on your example:

+---+---+---+
| A | B | C |
+---+---+---+
| D | E |
+---+---+    

Graph representation of this configuration is below:

The Enumerate('A', N('A')) function call was able to find more subgraphs, than you mentioned in your question - new ones are marked by asterisk:

A 
A B 
A B C 
A B C D    *
A B C D E 
A B C E 
A B D      *
A B D E 
A B E 
A D 
A D E 

As far as I understand your primary goal is to find subgraphs, satisfying some condition (sum of vertex weights = constant $M$). You can modify the function above to include checking this condition instead of simply printing $P$, for example:

if sum of vertex weights over P is equal to M
  output P
  return

Here you need to return from the function after the output because the vertex set $P$ expands with each recursive call, so the sum can only grow and become greater than this constant $M$ further on.

ADDITION. My C++ testing code is here.

Answer 2

I suggest you use a search algorithm on the following statespace: the state is a set of adjacent tiles whose numbers sum to 7 or less; it is possible to transition from state $s$ to $s'$ if $s'$ is obtained by adding to $s$ one tile that is adjacent to some tile in $s$. The initial state has the empty set $\emptyset$, and it can transition to any state containing a single tile.

Then, use a search algorithm, such a depth-first search or breadth-first search, to explore all states reachable from the initial state. You can store the reachable states in a hashtable. Whenever you discover a new reachable state, check if the numbers on its tiles sum to 7. If they do, you have found a valid solution.

As an optimization, you can use flood-fill to find all of the groups (connected components), then apply the above algorithm separately to each group.