swap white and black square Sixty four chess notation codes from a1 to h8 are placed randomly on each square of a standard 8x8 chessboard. Your task is to put the codes in the correct order as given in the diagram. In each step you can take one code from a white square and one code from a black square and exchange them.
What is the minimum number of steps that is sufficient to obtain the correct order from all possible initial positions?
 A: First observe that since you can swap the codes from $\it{any}$ white square and $\it{any}$ black square, the actual positions on the board don't matter, only the colors of the starting squares. Using this we can break the problem up into subproblems. 
Consider the problem on a $2x2$ board. The worst case scenario for the labels is that the labels that should be on black squares are on black squares (but the wrong ones), and similarly for the white squares. This is something you should check, but note that if a label starts on the wrong colored square, you can easily put it on the correct square in one move. In this worst case scenario, it takes $4$ moves to put every label in its correct place (check this too). 
Now consider the $8x8$ board in the problem. If the worst case scenario is again where the labels all start off on squares of the correct color but incorrect position, then we can just think of this as $16$ of the above subproblem by treating any $4$-square set consisting of two black squares and two white squares as a $2x2$ board sitting inside the $8x8$ board. We can do this because of the original observations that the actual positions on the board don't matter, only the colors.
Therefore after $16*4=64$ moves, we are sure to have everything in its correct place.
