## Friday, March 6, 2015

### Matrix permutation

I came across this interesting problem when I was solving a coursera assignment (8-puzzle) on Algorithms & Data Structures. This isn't related to the 8-puzzle where you need to visualize the solution as a game tree data structure.

I think this is related to the game tree.

Consider you have a $$2 \times 2$$ grid where there is an $$X$$ in one of the squares. You can make children of that figure only by moving $$X$$ it to the adjacent square either left, right, top, bottom. How many iterations do I need to ensure that $$X$$ has been through all the locations. It is possible that you can get the $$X$$ in a previous position by making a child of child (from the previous iteration: avoid such repetition.

Here is a figure that shows the case for the grid in question:

This is a very trivial example. What could be the solution for a larger grid?