Question 1
A few details that might need clarification...
1) Are tiles considered to be a match if they aren't at the extremities of a clear path? E.g:
############
### #
# ###O#### #
# ######O #
# ####### #
### ## ####
2) What about diagonals, are they considered adjacent? E.g:
############
### #
########## #
# #O#### #
####O##### #
######## ##
3) Can there be more than one pair of the same type on the grid, or just one?
Either way the solution to your problem will be fairly similar, so I'll assume all three are true for this explanation (I'll use C# as example). Read on for the full set of ideas...
Implementation
Part 1 - Storing and look up
After you finish filling your grid with tiles, you should scan each tile and group tiles of each type together to make it easier to lookup. I'll use a Dictionary, like so:
Dictionary<TileType, List<Tile>> tilesRegistry;
By the way I'll consider a Tile to have this structure:
class Tile
{
int x, y;
TileType type;
}
And as you go over each tile in the board, you'll register it on the dictionary doing something similar to:
void RegisterTile(Tile tile)
{
if(!tilesRegistry.Contains(tile.type))
{
tilesRegistry[tile.type] = new List<Point>();
}
tilesRegistry[tile.type].Add(tile);
}
Using this Dictionary you can easily find all tiles of any type on the board. For instance, if given one tile, you'd like to find if there's a match you could do:
Tile FindMatch(Tile tile)
{
List<Tile> tiles = tilesRegistry[tile.Type];
foreach(Tile t in tiles)
{
if(t == tile) continue;
if(AdjacentTiles(t, tile) || ConnectedTiles(t, tile))
{
return t;
}
}
return null;
}
I suppose you can figure out other uses for this registry to fulfill your needs.
Part 2 - Matching tiles and pathfinding
The other relevant detail of this implementation is how to create the AdjacentTiles and ConnectedTiles methods.
The AdjacentTiles method should be pretty obvious, just compare the X and Y coordinates of both tiles. The tricky one is ConnectedTiles.
Are you familiar with any pathfinding algorithm, such as A* (which I learned from this resource)?
Since your matching algorithm needs to find tiles connected by a clear path, your best course of action will probably be to use A*.
By treating the board as a sort of game map, with empty cells being considered as open, and other cells being blocked tiles (except for the ones of the tile type you're currently searching), you should be able to easily find the path between two tiles using A*.
Ideally you'll want to encapsulate it so that you may do:
List<Point> GetPath(Tile from, Tile to) {}
And it will return you the path (if any) between both cells.
Question 2
The solution to your second quest seems overly obvious. Start by adding a few pairs directly in adjacent positions on purpose. Then fill the remaining gaps randomly.