me and my friends are realising a game for our school project. The goal is to create a puzzle grid game with a solver. Our game will look like that in the idea : it's the best video I found.
So with some research I found only algorithm for a pathway (A*, Prim...) but nothing for changing possibilities and I would like to know if someone already found an idea or if I will have to go from scratch.
A* and Dijkstra's algorithm are both good choices for solving this problem, but you need to decide what graph to operate on.
These algorithms find a shortest path, and you want a (probably minimal) sequence of moves from the initial state to a solution, so you need graph in which a path from source to target represents such a sequence.
For instance, imagine a graph with a vertex for every possible board configuration, and an edge between any two vertices when you can get from one configuration to the other by one move. Now every path from the initial configuration to a solving configuration is a solving sequence of moves.
This works, but it is a very big graph -- your algorithm will run slowly and take a lot of memory.
For this problem, it's better to work row by row. If you've already set the pipes in the first n rows, then only the state of the last row affects how you have to set the rest. The "state" of the last row is the information about which cells connect to air, which connect to water, and which form a sealed connection to each other. If your puzzle is only 6 pipes across, then there will probably be only about 100 accessible states for every row.
So imagine a graph where you have vertices for all the accessible states of each row. A state in row i connects to a state in row i+1 if, given the state of row i, there's a way to orient the pipes in row i+1 to produce that state. Each edge can have a weight indicating the number of moves you have to make in row i+1 to get there.
Now a solving sequence of moves is represented by a path from the fixed start to a solving state in the last row. Again you can apply Dijkstra's or A* to find this path, and this time the graph is a reasonable size.
Note that in no case do you actually need to construct this graph. You just imagine that it exists and write your algorithm to traverse it using a compact representation of the puzzle. This is called operating on an implicit graph, and that's usually how simple graph algorithms are used in practice.