We are given a chessboard of size 'N' X 'N' . But it can contain any numbers of white-squares and black-squares , that too in any-order .
Say there are 'a'-squares of white color and 'b'-squares of black-color , then ,
[ a+b=n*n ]
We have to keep on making move with black-squares on the chessboard till there is no move left.
This is what happens in a move:-
1)We choose a black-square at co-ordinate:-(row,column) and move it to (row-1,column+1) , only if the co-ordinate (row-1,column+1) also contains a black-square . After it is moved to the new-position , the old-position,i.e, [row,column] becomes empty, i.e , its color turns to white .
OR
2)We choose a black-square at co-ordinate:-(row,column) and move it to (row-1,column-1) , only if the co-ordinate (row-1,column-1) also contains a black-square .After it is moved to the new-position , the old-position,i.e, [row,column] becomes empty, i.e , its color turns to white .
We have to end this game in least number of moves and the question is to find the sequence of those moves .
Lets denote black-square by '1' and white-square by '0' .. ...
Example:-
3X3 chessboard:-
0 1 0
1 0 1
0 0 0
Sequence of move(s) which ends the game in minimum number of moves : -
1)Move the black-square at [1,0] to [0,1]...Now the chessboard looks like this : -
0 1 0
0 0 1
0 0 0
2) We move the black-square at [1,2] to [0,1] and the chessboard looks like this:-
0 1 0
0 0 0
0 0 0
Now, there are no valid moves left and the game ends :-)
Given a chessboard of size 'N' x 'N' and any configuration of black and white-squares, how to find the sequence of moves which ends the game in minimum number of moves ?