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?