Find related blocks with a specific value in the grid

Question

I am having trouble finding an algorithm for my problem.

I have a grid of 8x8 blocks, each block has a value from 0 to 9. And I want to find collections of connected blocks that match a common value, for example 15. My first approach was to start from a border that worked perfectly. But when I run in the middle of the grid, my algorithm is lost.

Does anyone know a simple algorithm to use or can you point me in the right direction?

Thanks!

Answer 1

As far as I know, there is no simple algorithm for this. As for pointing in the right direction, an 8x8 grid is really just a special case of the chart, so I would start with graph traversal algorithms. I find that in such cases it sometimes helps to think about how to solve the problem for a smaller grid (say, 3x3 or 4x4), and then see if your algorithm will scale to "full size".

EDIT:
My proposed algorithm is a modified depth pass. To use it, you need to convert the grid to a graph. The graph should not be oriented, since the connected blocks are connected identically in both directions.

Each node graph represents one block containing the value of the block and the variable visited . Edge weights represent resistance to their edges. Set them by summing the values ​​of the nodes that they connect. Depending on the amount you are looking for, you can optimize it by removing edges that are guaranteed to fail. For example, if you are looking for 15, you can remove all edges with a weight of 16 or more.

The rest of the algorithm will be executed as many times as there are blocks, with each block being used as the initial block once. Go through the graph, following the lowest weighted edge from the current node, unless that leads you to the visited node. Push each visited node onto the stack and set its visited variable to true . Save the current amount for each subsequent path.

• Whenever the desired amount is reached, save the current path as one of your answers. Do not stop the crawl because the current node may be connected to zero.
• Whenever the amount exceeds the desired amount, return back by setting visited to false and pull the current node from the stack.
• Whenever all the edges for a given node have been examined, backtrack.

After analyzing each possible path from the given initial node, each answer containing this node is found. So, remove all edges touching the starting node and select a new starting node.

I have not yet fully analyzed the efficiency / runtime of this algorithm, but ... this is not good. (Consider the number of paths to look for in a graph containing all zeros.) However, this is much better than pure brute force.