Let's say we have a chessboard (i.e an $8×8$ grid). Let's assume each cell is identified by two coordinates (integer numbers) ranging from $1$ to $8$.
Assume to have a red pawn in position $(1, 1)$ and a green one in position $(8, 8)$. In other words, they are in the opposite corners of the board.
At each turn, the two pawns move (randomly) simultaneously. However, they can only move up, down, right and left with no diagonal moves allowed.
I am interested in finding whether or not the two pawns will eventually exchange cells. By exchanging cell I mean that the red pawn goes from $(x_1, y_1)$ to $(x_2, y_2)$ and the green one from $(x_2, y_2)$ to $(x_1, y_1)$ in the same turn.
By computer simulation I saw this is never happening. I wonder why is that the case.
If we allow diagonal moves, the two pawns will eventually exchange cells (according to my simulation) in an average of $48.6$ movements.
Best Answer
Hint: A chessboard has colors on it. Look at the colors of the squares that the pawns are on.