A match-3 game needs a way to detect when the player has lined up three or more identical tiles. The obvious case is a straight line of three or more tiles of the same type in a row or column. But what about L-shapes, T-shapes, and crosses? These are compound shapes formed by two intersecting runs, and detecting them correctly requires a bit more thought. In this article, I will show you how to write a match-3 solver that handles all of these cases using a three-phase approach: run detection, union-find grouping, and collection.
The supporting types
Before we get to the solver itself, let us define the types it operates on. These are simplified examples that contain only the data the solver cares about.
A Tile represents a type of gem, candy, fruit, or whatever your game’s matching item is. The only thing the solver cares about is the Id, which identifies tiles of the same type so that we can compare them.
public sealed class Tile
{
public int Id { get; init; }
public string DisplayName { get; init; }
}A Cell represents a position on the grid. It holds a reference to the Tile currently occupying it (if any).
public sealed class Cell
{
public int Column { get; set; }
public int Row { get; set; }
public Tile Tile { get; set; }
}When the solver finds a match, it returns a MatchGroup. Each group contains the tile ID that was matched and the list of cell indices that participate in the match. For a simple horizontal line of five identical tiles, one would get one group with five cell indices. For an L-shape, one would still get one group, because the horizontal and vertical runs intersect and share tiles.
public sealed class MatchGroup
{
public int TileId { get; set; }
public List<int> CellIndices { get; } = new();
}The three-phase approach
Detecting matches on a grid seems straightforward at first glance: just look for three consecutive identical tiles in a row or column. But compound shapes like L-shapes, T-shapes, and crosses are trickier because they consist of two or more runs that intersect at one or more cells. If one detects runs independently and returns each one as a separate match, he ends up with fragmented results that do not reflect the actual shape the player made.
My approach solves this by splitting detection into three phases:
- Run detection: Scan every row and column for maximal runs of 3+ consecutive tiles sharing the same tile ID, and flag each participating cell.
- Union-Find grouping: Adjacent flagged cells with the same tile ID are merged into disjoint sets using union by rank with path halving. This fuses intersecting horizontal and vertical runs into compound shapes automatically.
- Collection: Each distinct set root becomes a
MatchGroupcontaining the tile ID and every cell index in the group.
Let us build the solver step by step.
Starting with the empty class
We begin with the MatchSolver class skeleton and the properties that expose results to the caller. The Matches property holds the match groups found by the most recent Solve call, and HasMatches is a convenience property that returns true when at least one match was found.
public sealed class MatchSolver
{
private readonly List<MatchGroup> _matches = new();
public IReadOnlyList<MatchGroup> Matches
{
get => _matches;
}
public bool HasMatches
{
get => _matches.Count > 0;
}
}I chose to store results in a List<MatchGroup> and expose it through IReadOnlyList<MatchGroup> instead of returning a fresh list on every call. This avoids allocating a new collection each time the solver runs, which matters when one is calling it frequently (e.g., every frame to check whether a swap produced a match).
Grid dimensions and capacity management
The solver needs to know the grid’s dimensions to allocate its internal buffers correctly and to iterate over rows and columns. I store the column count, row count, and total cell count, and I provide an EnsureCapacity method that allocates or resizes the buffers as needed.
private int _columnCount;
private int _rowCount;
private int _cellCount;
private int[] _parent = Array.Empty<int>();
private int[] _rank = Array.Empty<int>();
private bool[] _matched = Array.Empty<bool>();
public void EnsureCapacity(int columnCount, int rowCount)
{
_columnCount = columnCount;
_rowCount = rowCount;
_cellCount = columnCount * rowCount;
if (_parent.Length >= _cellCount) return;
_parent = new int[_cellCount];
_rank = new int[_cellCount];
_matched = new bool[_cellCount];
}The early return is important: if the new cell count does not exceed the previous high-water mark, we reuse the existing buffers. This avoids repeated allocations when the grid size does not change between calls, which is the common case.
The three arrays serve the following purposes:
_parent: The Union-Find parent array. Each element either points to itself (it is a root) or points to another element closer to the root._rank: The rank array used by union by rank. It approximates the height of each tree in the Union-Find forest._matched: A boolean flag array. After Phase 1,truemeans the cell participates in at least one run of 3+ identical tiles.
The Solve method
The Solve method is the main entry point. It orchestrates the three phases in order.
public void Solve(Cell[] cells)
{
RecycleGroups();
ResetBuffers();
MarkHorizontalRuns(cells);
MarkVerticalRuns(cells);
UnionAdjacentMatchedCells(cells);
CollectGroups(cells);
}RecycleGroups returns previously created MatchGroup objects to an internal pool so they can be reused, and ResetBuffers clears the Union-Find and matched-flag arrays. Then the three phases execute in sequence. Let us look at each one.
Resetting buffers
Before each solve, we need to reset the Union-Find state and clear the match flags.
private void ResetBuffers()
{
Array.Clear(_matched, 0, _cellCount);
Array.Clear(_rank, 0, _cellCount);
for (int i = 0; i < _cellCount; i++)
{
_parent[i] = i;
}
}Each element starts as its own parent (a singleton set) with rank zero. This is the standard Union-Find initialisation. Clearing _matched ensures we do not carry over stale flags from a previous solve.
Phase 1: Run detection
The goal of this phase is to flag every cell that participates in a run of three or more consecutive tiles with the same ID. We do this separately for horizontal runs and vertical runs.
Horizontal runs
We scan each row from left to right. For every row, we track the start of the current run and extend it as long as the tile ID stays the same. When the run breaks (or we reach the end of the row), we check its length; if it is 3 or more, we flag every cell in that run.
private void MarkHorizontalRuns(Cell[] cells)
{
for (int row = 0; row < _rowCount; row++)
{
int offset = row * _columnCount;
int runStart = 0;
for (int col = 1; col <= _columnCount; col++)
{
if (col < _columnCount && GetTileId(cells, offset + col) == GetTileId(cells, offset + col - 1))
{
continue;
}
if (col - runStart >= 3)
{
MarkRun(offset + runStart, 1, col - runStart);
}
runStart = col;
}
}
}The loop goes from col = 1 to col <= _columnCount rather than col < _columnCount. The extra iteration at col == _columnCount acts as a sentinel: it forces the end-of-run check for any run that reaches the right edge of the grid. This avoids duplicating the end-of-run logic after the loop.
When we detect a valid run, we call MarkRun with the start index, a stride of 1 (horizontal, moving one cell at a time), and the run length.
Vertical runs
The same logic, but scanning columns top to bottom. The stride is now _columnCount because moving one row down means jumping an entire row’s worth of cells in the flat array.
private void MarkVerticalRuns(Cell[] cells)
{
for (int col = 0; col < _columnCount; col++)
{
int runStart = 0;
for (int row = 1; row <= _rowCount; row++)
{
if (row < _rowCount && GetTileId(cells, row * _columnCount + col) == GetTileId(cells, (row - 1) * _columnCount + col))
{
continue;
}
if (row - runStart >= 3)
{
MarkRun(runStart * _columnCount + col, _columnCount, row - runStart);
}
runStart = row;
}
}
}MarkRun
A helper that flags every cell in a detected run. The stride parameter controls whether we are moving horizontally (stride 1) or vertically (stride _columnCount).
private void MarkRun(int start, int stride, int length)
{
for (int i = 0; i < length; i++)
{
_matched[start + stride * i] = true;
}
}After Phase 1, _matched[i] is true if and only if cell i belongs to at least one horizontal or vertical run of 3+ identical tiles.
Phase 2: Union-Find grouping
This is where the magic happens. After Phase 1, we have a set of flagged cells, but a cell can be flagged from both a horizontal and a vertical run. An L-shape, for example, consists of a horizontal run and a vertical run that share a corner cell. We need to merge all connected flagged cells into groups.
We do this with a Union-Find (disjoint set) data structure. The idea is simple: each cell starts in its own set. When we find two adjacent flagged cells that have the same tile ID, we merge their sets. By the time we have checked all adjacent pairs, every connected component of flagged cells with the same tile ID is in one set.
Finding set roots
The Find method locates the root (representative) of a set using path halving. Path halving is a variant of path compression where, instead of flattening the entire path to the root in one pass, every node on the search path is moved to point to its grandparent. This achieves nearly the same amortised performance as full path compression but is simpler to implement iteratively.
private int Find(int x)
{
while (_parent[x] != x)
{
_parent[x] = _parent[_parent[x]];
x = _parent[x];
}
return x;
}Path halving reduces the amortised time complexity of each Find operation to nearly O(1), which makes the overall Union-Find operations O(n · α(n)) where α is the inverse Ackermann function, effectively constant for any practical input size.
Merging sets
The Union method merges two sets using union by rank. The rank is an upper bound on the height of the tree. By always attaching the shorter tree under the taller one, we keep the trees shallow, which ensures Find stays fast.
private void Union(int a, int b)
{
int rootA = Find(a);
int rootB = Find(b);
if (rootA == rootB) return;
if (_rank[rootA] < _rank[rootB])
{
_parent[rootA] = rootB;
}
else if (_rank[rootA] > _rank[rootB])
{
_parent[rootB] = rootA;
}
else
{
_parent[rootB] = rootA;
_rank[rootA]++;
}
}If both roots have the same rank, we arbitrarily choose one to be the new root and increment its rank. This is the standard union-by-rank strategy.
Scanning for adjacent matches
Now we scan the grid and merge adjacent flagged cells that share the same tile ID. We only check the cell to the right and the cell below to avoid processing each pair twice.
private void UnionAdjacentMatchedCells(Cell[] cells)
{
for (int row = 0; row < _rowCount; row++)
{
for (int col = 0; col < _columnCount; col++)
{
int index = row * _columnCount + col;
if (!_matched[index]) continue;
int tileId = GetTileId(cells, index);
if (col + 1 < _columnCount)
{
int right = index + 1;
if (_matched[right] && GetTileId(cells, right) == tileId)
{
Union(index, right);
}
}
if (row + 1 >= _rowCount) continue;
int below = index + _columnCount;
if (_matched[below] && GetTileId(cells, below) == tileId)
{
Union(index, below);
}
}
}
}Two things are worth noting here. First, we skip cells that are not flagged: unflagged cells are not part of any run, so they cannot be part of a compound match. Second, we check that the tile ID matches before merging, which prevents a flagged cell from one horizontal run of type A from merging with an adjacent flagged cell from a vertical run of type B.
Phase 3: Collection
After the Union-Find phase, every flagged cell belongs to exactly one set. We now need to turn those sets into MatchGroup objects that the caller can actually use.
private readonly Dictionary<int, MatchGroup> _rootToGroup = new();
private void CollectGroups(Cell[] cells)
{
_rootToGroup.Clear();
for (int i = 0; i < _cellCount; i++)
{
if (!_matched[i]) continue;
int root = Find(i);
if (!_rootToGroup.TryGetValue(root, out MatchGroup group))
{
group = RentGroup();
group.TileId = GetTileId(cells, i);
_rootToGroup[root] = group;
_matches.Add(group);
}
group.CellIndices.Add(i);
}
}We iterate over every cell, skip unflagged ones, and look up the root of the flagged cell’s set. If we have not seen that root yet, we rent a MatchGroup from the pool (more on that shortly), store the tile ID, and add it to the _matches list. We then add the cell index to the group’s CellIndices list.
The _rootToGroup dictionary maps set roots to the MatchGroup objects they belong to. This avoids a second pass over the cells and ensures each set produces exactly one group.
Object pooling with RentGroup and RecycleGroups
If the solver is called frequently (for example, on every swap or every frame to check for chain reactions), creating and discarding MatchGroup objects on every call would put unnecessary pressure on the garbage collector. To avoid that, I use a simple object pool.
private readonly Stack<MatchGroup> _groupPool = new();
private MatchGroup RentGroup()
{
if (_groupPool.Count <= 0) return new MatchGroup();
MatchGroup group = _groupPool.Pop();
group.TileId = -1;
group.CellIndices.Clear();
return group;
}
private void RecycleGroups()
{
foreach (MatchGroup group in _matches)
{
_groupPool.Push(group);
}
_matches.Clear();
}When Solve is called, RecycleGroups pushes all the groups from the previous solve back into the pool. When CollectGroups needs a new group, RentGroup pops one from the pool if available, or creates a fresh one if the pool is empty. This means that after the first solve, the groups are reused rather than allocated and collected, which eliminates per-frame garbage.
Note that RecycleGroups is called at the beginning of Solve, before ResetBuffers. This means the previous solve’s results are invalidated: the Matches list is cleared and the groups are returned to the pool. This is intentional: the solver’s contract is that results are valid until the next call to Solve.
Handling empty cells
One last detail: what about cells that do not have a tile? In a match-3 game, cells can be empty after tiles have been matched and removed, but before new tiles have fallen into place. We need to make sure empty cells do not form spurious runs.
private static int GetTileId(Cell[] cells, int index)
{
Tile tile = cells[index].Tile;
return tile != null ? tile.Id : ~index;
}If the cell’s tile is null, we return the bitwise complement of the cell’s index. The bitwise complement of any non-negative integer is negative, and no two indices produce the same complement. This guarantees that two empty cells at different positions will never compare as equal, which prevents them from forming runs across gaps in the grid.
An alternative approach would be to return a sentinel value like -1 for all empty cells. But that would cause adjacent empty cells to be treated as having the same tile ID, potentially forming a “run” of empty cells, which is incorrect. Using ~index is a neat trick that avoids this problem entirely.
The complete solver
Here is the full MatchSolver class, for reference:
public sealed class MatchSolver
{
private int _columnCount;
private int _rowCount;
private int _cellCount;
private int[] _parent = Array.Empty<int>();
private int[] _rank = Array.Empty<int>();
private bool[] _matched = Array.Empty<bool>();
private readonly List<MatchGroup> _matches = new();
private readonly Dictionary<int, MatchGroup> _rootToGroup = new();
private readonly Stack<MatchGroup> _groupPool = new();
public IReadOnlyList<MatchGroup> Matches => _matches;
public bool HasMatches => _matches.Count > 0;
public void EnsureCapacity(int columnCount, int rowCount)
{
_columnCount = columnCount;
_rowCount = rowCount;
_cellCount = columnCount * rowCount;
if (_parent.Length >= _cellCount) return;
_parent = new int[_cellCount];
_rank = new int[_cellCount];
_matched = new bool[_cellCount];
}
public void Solve(Cell[] cells)
{
RecycleGroups();
ResetBuffers();
MarkHorizontalRuns(cells);
MarkVerticalRuns(cells);
UnionAdjacentMatchedCells(cells);
CollectGroups(cells);
}
private void ResetBuffers()
{
Array.Clear(_matched, 0, _cellCount);
Array.Clear(_rank, 0, _cellCount);
for (int i = 0; i < _cellCount; i++)
{
_parent[i] = i;
}
}
private void MarkHorizontalRuns(Cell[] cells)
{
for (int row = 0; row < _rowCount; row++)
{
int offset = row * _columnCount;
int runStart = 0;
for (int col = 1; col <= _columnCount; col++)
{
if (col < _columnCount && GetTileId(cells, offset + col) == GetTileId(cells, offset + col - 1))
{
continue;
}
if (col - runStart >= 3)
{
MarkRun(offset + runStart, 1, col - runStart);
}
runStart = col;
}
}
}
private void MarkVerticalRuns(Cell[] cells)
{
for (int col = 0; col < _columnCount; col++)
{
int runStart = 0;
for (int row = 1; row <= _rowCount; row++)
{
if (row < _rowCount && GetTileId(cells, row * _columnCount + col) == GetTileId(cells, (row - 1) * _columnCount + col))
{
continue;
}
if (row - runStart >= 3)
{
MarkRun(runStart * _columnCount + col, _columnCount, row - runStart);
}
runStart = row;
}
}
}
private void MarkRun(int start, int stride, int length)
{
for (int i = 0; i < length; i++)
{
_matched[start + stride * i] = true;
}
}
private void UnionAdjacentMatchedCells(Cell[] cells)
{
for (int row = 0; row < _rowCount; row++)
{
for (int col = 0; col < _columnCount; col++)
{
int index = row * _columnCount + col;
if (!_matched[index]) continue;
int tileId = GetTileId(cells, index);
if (col + 1 < _columnCount)
{
int right = index + 1;
if (_matched[right] && GetTileId(cells, right) == tileId)
{
Union(index, right);
}
}
if (row + 1 >= _rowCount) continue;
int below = index + _columnCount;
if (_matched[below] && GetTileId(cells, below) == tileId)
{
Union(index, below);
}
}
}
}
private int Find(int x)
{
while (_parent[x] != x)
{
_parent[x] = _parent[_parent[x]];
x = _parent[x];
}
return x;
}
private void Union(int a, int b)
{
int rootA = Find(a);
int rootB = Find(b);
if (rootA == rootB) return;
if (_rank[rootA] < _rank[rootB])
{
_parent[rootA] = rootB;
}
else if (_rank[rootA] > _rank[rootB])
{
_parent[rootB] = rootA;
}
else
{
_parent[rootB] = rootA;
_rank[rootA]++;
}
}
private void CollectGroups(Cell[] cells)
{
_rootToGroup.Clear();
for (int i = 0; i < _cellCount; i++)
{
if (!_matched[i]) continue;
int root = Find(i);
if (!_rootToGroup.TryGetValue(root, out MatchGroup group))
{
group = RentGroup();
group.TileId = GetTileId(cells, i);
_rootToGroup[root] = group;
_matches.Add(group);
}
group.CellIndices.Add(i);
}
}
private static int GetTileId(Cell[] cells, int index)
{
Tile tile = cells[index].Tile;
return tile != null ? tile.Id : ~index;
}
private MatchGroup RentGroup()
{
if (_groupPool.Count <= 0) return new MatchGroup();
MatchGroup group = _groupPool.Pop();
group.TileId = -1;
group.CellIndices.Clear();
return group;
}
private void RecycleGroups()
{
foreach (MatchGroup group in _matches)
{
_groupPool.Push(group);
}
_matches.Clear();
}
}Wrapping up
The three-phase approach of run detection, union-find grouping, and collection cleanly separates concerns and makes the solver easy to reason about. The union-find data structure handles the tricky part of fusing intersecting runs into compound shapes, and object pooling keeps garbage collection pressure low when the solver is called frequently.
The overall time complexity is O(n · α(n)) where n is the number of cells and α is the inverse Ackermann function, which is effectively constant for any realistic grid size. The space complexity is O(n) for the three buffer arrays.
Thanks for reading!