The value of (N) for this problem is between [1,100].
There is a chessboard with N rows (numbered 1 through N) and N columns (numbered 1 through N) . Let's denote a cell in row r and column c of the chessboard by (r,c). Only a few pawns are placed on the chessboard and nothing else.
You may perform any number of moves in any order. In one move, you must take one pawn and capture another pawn with it; just like in standard chess, a pawn in a cell (r,c) may capture only pawns in cells (r−1,c−1) or (r−1,c+1). The captured pawn is removed and the pawn that captured it takes its place. It is not allowed to move pawns without capturing. Unlike in standard chess, the pawns do not have colors, so it is possible to use all pawns to capture and all pawns can be captured.
The number of moves you can make is finite, so the game can always reach a state where you have no valid moves. Find the shortest possible sequence of moves such that there are no more valid moves afterwards.
Example:-
3X3 chessboard:-
'O' denotes pawn and '.' denotes empty cell.
. O .
O . O
. . .
Solution:-
2(moves required):-
2 1 R--->Pawn at (2,1) captures pawn at upper right cell.
2 3 L--->Pawn at (2,3) captures pawn at upper left cell.
After the first move, the chessboard becomes
. O .
. . O
. . .
and after the second move, it becomes
. O .
. . .
. . .