Here is an animation I made of how the game plays. https://i.imgur.com/KRXCOyD.mp4 It's an empty board with two tiles (T) showing how they interact with each other. There can also be walls (W) that act like the tiles but they can't be moved — they only stop the moveable tiles.

You can only move one tile at a time. When you move it, it slides until it stops. Tiles could theoretically be places anywhere on the board, but I'm trying to find what I call starting positions. In graph-theory, they create a cycle and once you get into a cycle, you can't escape. I don't want to start outside this cycle. So if I start the puzzle in an invalid state (e.i. not on starting positions) I would eventually get into a valid state, but I don't want it to ever be invalid.

For the animation, there's 28 valid starting positions. If it were just one tile, there would be only 4.

Here's how I think it could be done. Let's just focus on one for now.

Here we have a moveable tile in the top left corner and a wall on the bottom row.

From the start, I could move down or right. From down, I could only move back up. From the right, I could move down, left, and then up. From the final up position, I could move left or right but notice these are one-way.

If I number the cells of the board 1 through 25 like this:

Then the directed graph for all the starting positions would look like this:

Notice how I can reach any node from any other node. I might have to take a detour to get back to 3 but it's possible.

If I started in the middle which is a non-valid position:

The graph ends up looking like this:

Here, 11, 13, and 15 are invalid starting positions. It's difficult to see, but if you start on any of them and then move to a valid position, you can never get back to an invalid position.

I'm trying to make an algorithm that can get all the valid starting positions. Here's how I think I could do it. I'm hoping somebody can tell me if I'm right or wrong, or if there's a better way. I'd start with a depth-first or breadth-first search. This could generate a list of candidates. Then for each cell that wasn't visited, do another search until I have a list of lists of candidates. Then I would union all the lists together. Maybe that would work, I'm not sure.

I don't know if I could use something like Tarjan's Algorithm for strongly connected components or if I just need to cycle detection algorithm.

I'm thinking my solution might not work, because it's possible to have more than 1 list of valid starting positions. Consider the following:

Each tile forms their own cycle. For these examples, I'm only considering 1 or 2 tiles, but in reality, there can be between 1 and empty cells - 1 tiles. There needs to be at least one in order to move to. And I understand these graphs can get quiet large.