Check adjacency of tiles in a grid

Question

I am working on a sliding block puzzle solver, and I would like to extend the game to a grid with arbitrary sides and blocks of all kinds of shapes. I define a grid with a given height and width and I translate that into a dictionary with a running index as the key and a boolean as the value (true if position is tiled, otherwise false).

Example with running index:

|0|1|2|
|3|4|5|
|6|7|8|

Example block and its corresponding dictionary (Xs denote tiled positions)

|0|1|X|
|3|X|X|
|X|X|8|

{
   0: false, 1: false, 2: true,
   3: false, 4: true,  5: true,
   6: true,  7: true,  8: false
}

As I plan to randomly create block layouts, I want to test the validity of an arbitrary layout. One of the requirements for a block to be valid, is that all the tiles are connected through adjacent neighbours.

Valid block:

|X|X|X|
|X| |X|
|X| | |

Invalid block (blocks 1 and 5 are not connected):

|X|X| |
| | |X|
| | |X|

At first, I thought I could solve this by getting the list of adjacent indices of every tiled position in the block and to check if every other tiled index is included in at least one of adjacency lists. But the invalid example above is already a case where that does not work.

How could I check if all the tiles are somehow connected to each other?

PS: This question seems independent of the language I'm using, but since I'm using C# I'll add that tag just to be sure.

Answer 1

You can start from any of the tiles and run a DFS (Depth First Search) . If you can visit all the tiles during the DFS your tiles are connected . Otherwise not .

Here is a pseudo code

dfs(x,y):
   visited[x][y] = true
   for each position in your adjacency list: ## up,down,left,right
      if(visited[newX][newY]==false and grid[newX][newY] is a tile and newX , newY both is in the grid ):
          dfs(newX,newY)

Basically just start from a tile and only move to another tile using the left / right / up / down move as long as it is possible . If they are not connected , you will end up before every one of the tile is visited .