graph principle – How can I discover legitimate beginning positions for my puzzle sport?

Right here is an animation I manufactured from how the sport performs. https://i.imgur.com/KRXCOyD.mp4 It is an empty board with two tiles (T) displaying how they work together with one another. There will also be partitions (W) that act just like the tiles however they cannot be moved — they solely cease the moveable tiles.

You possibly can solely transfer one tile at a time. If you transfer it, it slides till it stops. Tiles may theoretically be locations anyplace on the board, however I am looking for what I name beginning positions. In graph-theory, they create a cycle and when you get right into a cycle, you’ll be able to’t escape. I do not need to begin outdoors this cycle. So if I begin the puzzle in an invalid state (e.i. not on beginning positions) I might ultimately get into a legitimate state, however I do not need it to ever be invalid.

For the animation, there’s 28 legitimate beginning positions. If it have been only one tile, there could be solely 4.

This is how I believe it could possibly be achieved. Let’s simply give attention to one for now.

Right here we’ve got a moveable tile within the prime left nook and a wall on the underside row.

From the beginning, I may transfer down or proper. From down, I may solely transfer again up. From the suitable, I may transfer down, left, after which up. From the ultimate up place, I may transfer left or proper however discover these are one-way.

If I quantity the cells of the board 1 by 25 like this:

Then the directed graph for all of the beginning positions would appear like this:

Discover how I can attain any node from every other node. I might need to take a detour to get again to three but it surely’s potential.

If I began within the center which is a non-valid place:

The graph finally ends up wanting like this:

Right here, 11, 13, and 15 are invalid beginning positions. It is tough to see, however should you begin on any of them after which transfer to a legitimate place, you’ll be able to by no means get again to an invalid place.

I am attempting to make an algorithm that may get all of the legitimate beginning positions. This is how I believe I may do it. I am hoping anyone can inform me if I am proper or fallacious, or if there’s a greater method. I would begin with a depth-first or breadth-first search. This might generate a listing of candidates. Then for every cell that wasn’t visited, do one other search till I’ve a listing of lists of candidates. Then I might union all of the lists collectively. Possibly that may work, I am unsure.

I do not know if I may use one thing like Tarjan’s Algorithm for strongly linked elements or if I simply must cycle detection algorithm.

I am considering my answer may not work, as a result of it is potential to have greater than 1 listing of legitimate beginning positions. Take into account the next:

Every tile types their very own cycle. For these examples, I am solely contemplating 1 or 2 tiles, however in actuality, there will be between 1 and empty cells – 1 tiles. There must be at the very least one with a view to transfer to. And I perceive these graphs can get quiet massive.