Chess Mate Attack is a mobile puzzle game released earlier this year. Each of its 90 (at time of writing) levels follows the same basic principles:
- Play takes place on an $m×n$ chessboard, whose squares are either empty or occupied by pieces (red or blue), walls, or floors.
- You control whichever blue pieces are present, and move them as in chess, with the caveat that after every move, pieces fall until they are blocked by a wall, a floor, or a piece of the same color. If a piece lands in a space occupied by a piece of a different color, the opposing piece is captured and removed from play. (Opposing pieces may also be captured in the "normal" fashion.)
- Walls can be jumped over by knights, and floors can be passed through in any direction by any piece but cannot be fallen through. (Neither of these facts are relevant to this puzzle.)
- The goal is to capture the red King.
Consider the following board, taken from the game, where yellow boxes are walls and the two pieces are the red King and blue Queen:
In the original game, the red King remains stationary, and can be captured on the fourth move. However, if the red King moves after each of your moves (subject to gravity, just like you), capturing takes seven moves. Can you find the best strategies for both players?