# Isolating groups on a board

This topic is 1075 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Given an n by n board of squares, on which a square can be any of x colours, are there efficient algorithms for isolating groups, where a group consists of 1 or more squares of the same colour?

/*
A 7 x 7, nine 'colour' grid.

1 1 2 5 3 4 5
1 4 1 3 5 5 5
1 4 6 8 7 2 2
2 1 2 2 3 4 5
6 7 8 9 5 6 6
1 1 3 5 3 8 9
1 3 5 8 7 3 2
*/


For instance, in the above grid, there is a group of 6 1s in the top left corner.

I wasn't sure exactly in which forum this belonged, but it feels like it should reduce to a known (hopefully solved) math problem?

Edited by Mats1

##### Share on other sites
The standard method to handle this is called union-find. Edited by Álvaro

##### Share on other sites

You will probably want to

1) find unassigned cell (linear search will work if this isnt a bottleneck - maybe do each search from where previous left off to not search same stuff every time)

2) flood fill from that cell until you find all cells in the connected group of cells (while forming the group which could be by assigning the group ID to each cell, or adding each cell to some group objects list of cells)

3) repeat

##### Share on other sites
Here's some code, adapted from my go board:

#include <iostream>

// Size of the board and the extended board (with padding)
int const N = 7;
int const XN = N + 2;
int const XN2 = XN * XN;

auto const neighboring_directions = {-XN-1, -XN, -XN+1, -1, +1, +XN-1, +XN, +XN+1};

struct Board {
int array[XN2];
int chain_id[XN2];
int chain_size[XN2];
int next_in_chain[XN2];

Board();

void coalesce_chains(int p1, int p2);

void place_color(int point, int color);
};

Board::Board() {
for (int i = 0; i < XN2; ++i) {
array[i] = -1;
chain_id[i] = 0;
chain_size[i] = 0;
next_in_chain[i] = 0;
}
}

void Board::coalesce_chains(int p1, int p2) {
if (chain_size[p1] < chain_size[p2])
std::swap(p1, p2);
int chain_id1 = chain_id[p1];
int chain_id2 = chain_id[p2];

int p = p2;
do {
chain_id[p] = chain_id1;
p = next_in_chain[p];
} while (p != p2);

int n1 = next_in_chain[p1];
int n2 = next_in_chain[p2];
next_in_chain[p1] = n2;
next_in_chain[p2] = n1;

chain_size[chain_id1] += chain_size[chain_id2];
}

void Board::place_color(int point, int color) {
// Set up this point as its own chain
array[point] = color;
chain_id[point] = point;
chain_size[point] = 1;
next_in_chain[point] = point;

// Coalesce neighboring chains
for (int offset : neighboring_directions) {
if (array[point + offset] == color && chain_id[point + offset] != chain_id[point])
coalesce_chains(point + offset, point);
}
}

int main() {
int map[XN2] = {
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 2, 5, 3, 4, 5, 0,
0, 1, 4, 1, 3, 5, 5, 5, 0,
0, 1, 4, 6, 8, 7, 2, 2, 0,
0, 2, 1, 2, 2, 3, 4, 5, 0,
0, 6, 7, 8, 9, 5, 6, 6, 0,
0, 1, 1, 3, 5, 3, 8, 9, 0,
0, 1, 3, 5, 8, 7, 3, 2, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0
};

Board board;

for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
int point = i * XN + j;
board.place_color(point, map[point]);
}
}

for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
int point = i * XN + j;
std::cout << board.chain_id[point] << ' ';
}
std::cout << "    ";
for (int j = 1; j <= N; ++j) {
int point = i * XN + j;
std::cout << (board.chain_size[board.chain_id[point]]) << ' ';
}
std::cout << '\n';
}
}


Once you have told the Board class what all the colors are, you can get the chain id for each point (chain_id) and you can also loop over the elements in a chain using next_in_chain.

1. 1
2. 2
3. 3
Rutin
19
4. 4
khawk
14
5. 5
frob
12

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633659
• Total Posts
3013208
×