A-star is not limited to performing just pathfinding; consider it more a graph traversal algorithm (which fits well with this state space). I would use one variant in particular, IDA-star, for solving this game. If we consider one or more nodes connected together as a "cluster", starting with an "empty cluster", the start state is a set of clusters, and the end state is one single cluster that represents a cycle. A "move" would connect two clusters together.
There is nothing particularly publish-worthy although it would make an interesting state space for a graduate-level AI class assignment.
(Another state space -- game -- that we can use A-star to solve are sliding tile games, which have nothing outwardly to do with pathfinding per se.)
What you are describing is exhaustive search on the state space and is orders of magnitude slower than the randomized algorithm, especially when executed by humans (which is why I added the qualifier "efficiently"). Also, A* is for finding the shortest path, and the length of the path in this case is irrelevant. In fact the length of all paths is the same.
There is nothing particularly publish-worthy although it would make an interesting state space for a graduate-level AI class assignment.
(Another state space -- game -- that we can use A-star to solve are sliding tile games, which have nothing outwardly to do with pathfinding per se.)