Note:- I've solved the above problem with back-tracking approach,by trying out all different ways, I am in search of a very efficient way/pattern.
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 ?
One way you can view this problem would be as a graph traversal. Since we are looking for the shortest move, we can exploit our knowledge of graph traversal algorithms and consider using a breadth-first traversal.
We are going to need to be able to do a couple of things to achieve this:
Now that we have this, let's see how we can map this problem to a graph traversal problem.
Then the process of finding the shortest path to a terminal positions would look like this (starting at the root node):
The magic of the breath-first traversal kicks in here. From here we repeat this process of expanding a node, checking for terminal configurations, and going down a level in the graph if we don't find such a configuration.
Once we do find a terminal configuration, we know that the path (edges representing moves made) from our root node (initial configuration) to our terminal node (game over position), is the shortest. All we do now is count the number of edges back to the root node, and we know what the minimum number of moves is.