In Super Mario Galaxy 2, the last level of the game has a part where you have to step on switches, which change color when stepped on. In order to progress in the level, every switch must be changed. The color will only change one time when you step on it. To clarify, if you step on it the color changes. To change the color again, you have to step on a different switch and step back on the original one.
Here's a video of what I'm talking about: https://www.youtube.com/watch?v=dpGjKEt8wmw#t=34
I was wondering what path finding algorithm I could apply to it to find the fastest way through this part. Right off the bat I thought of A*, but I don't if it would apply since I need to hit every node and the goal node is the same as the source.
If I understood the problem correctly, you want to step on every block once and also step on all the blocks.
So if you think of this as a graph, with every block being represented by a vertex (and every pair of adjacent blocks -horizontally, vertically or diagonally- consists and edge), you need to visit every vertex once and return to the source vertex (i.e. form a cycle). But that's a Hamiltonian Cycle which is NP-Complete (and you need dynamic programming to solve it).