Manni and Miku play the following game with rooks on an chessboard. At the beginning of the game, Miku places 8 rooks to the squares of the board according to his will. Then both players make moves alternately, Manni starts. On any move, each player shifts exactly one rook along a rank or file (i.e. row or column) by one or more squares in one direction. If a rook moves to a square that contains another rook, the latter is removed from the board; it is not allowed to move a rook over another. A player who is the first to remove a rook from the board wins; however, neither moving nor removing a rook that was moved by the opponent on his last move is allowed. Does either of the players have a winning strategy and if yes then which of them?
Solution
We show at first that Miku can play in such a way that Manni can never remove a rook. Let there be one rook in each rank and file in the initial configuration. Suppose that Manni moves a rook from square to square . As a consequence, each file contains one rook but there are no rooks in rank and two rooks in rank ; let a rook be on square , . Let Miku move the rook from square to square . After that, there is one rook in each rank and file again. In the case of Manni's move in the perpendicular direction, Miku's reply would be analogous. In such a way, Miku can reply to all Manni's following moves.
Now we show that also Manni can play so that Miku never wins. If there are two or more rooks on one rank or file in the initial configuration then Manni can remove one of them and win immediately. Therefore assume that initially there is one rook on each rank and file. Let there be rooks on squares and . Manni can move the rook from to square . As Miku is not allowed to remove this rook but Manni threatens to remove the rook on on the next move, Miku must move this rook to some square . If , Manni can win by moving the rook from square to square and removing either of the other rooks on rank on the next move. If , then there is one rook in each rank and file again and Manni can continue with the same strategy.