Problem Statement |
| | Antichess, also called Suicide Chess, is a chess variant in which the objective is to lose all of your pieces. The rules of the game are the same as those of chess, except that capturing is compulsory. In other words, when a player has the opportunity to capture an opponent's piece, he must do it. If the player has multiple choices for capturing during a single turn, he may choose any single one. The king plays no special role in the game; it can be captured like any other piece. Because of the forced capture rule, antichess games often have a long sequence of forced captures by one player.
In this problem, we are given an end-game position - specifically, the case when a player has only pawns left and the other has a queen. Considering we are the white player controlling the pawns and we always make the first move, we are interested in how many consecutive pawns we can force our opponent to capture. The game ends when either the queen has been captured, the queen can no longer capture, there are no pawns left, or there is a stalemate. A stalemate is produced if, on white's turn, there are no valid pawn moves.
The queen may move in any straight line, horizontally, vertically, or diagonally. The queen may not jump over other pieces. In other words, all squares between the square where the queen starts her move and where the queen ends her move must be empty. When the square where the queen ends her move contains a pawn of the opponent, then this piece is captured.
A pawn can only move one row straight forward, to a higher row (rows are numbered from 1 to 8 and columns from 'a' to 'h'). Pawns on row 2 can also move 2 rows straight forward. Pawns on row 8 can no longer move. As in the case of the queen, the pawn is not allowed to jump over other pieces. When capturing, the pawn goes one square diagonally forward onto the opponent's captured piece.
You are given a String[] white, where each element contains 2 characters describing the position of a pawn: the first character is a lowercase letter between 'a' and 'h', and the second character is a digit between '2' and '7'. You are also given a String black that contains 2 characters describing the position of the queen: the first character is a lowercase letter between 'a' and 'h', and the second character is a digit between '1' and '8'. Return the highest number of pawns you can force your opponent to capture, considering their play is optimal.
|
| |
Definition |
| | | Class: | AntiChess | | Method: | sacrifice | | Parameters: | String[], String | | Returns: | int | | Method signature: | int sacrifice(String[] white, String black) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Both white and black sides must capture if they can. |
| - | If a pawn reaches the 8th row, instead of promoting, it just gets stuck. |
| - | Like in a normal chess game, a pawn on the 2th row can either move to the 3th row or to the 4th row on a single turn. In all the other cases, it can only advance a single row. |
| |
Constraints |
| - | white contains between 1 and 8 elements, inclusive. |
| - | Each element of white contains exactly 2 characters. |
| - | The first character in each element of white is a lowercase letter between 'a' and 'h', inclusive. |
| - | The second character in each element of white is a digit between '2' and '7', inclusive. |
| - | No two pawns will share a column. |
| - | black contains exactly 2 characters. |
| - | The first character in black is a lowercase letter between 'a' and 'h', inclusive. |
| - | The first character in black is a digit between '1' and '8', inclusive. |
| - | black is different than any element of white . |
| |
Examples |
| 0) | |
| | {"a2","c2","d2","e3","h4"} | "b6" |
| Returns: 5 | One possibility is to move the pawn from a2 to a4. The black is forced to take the pawn on e3, but then the white is forced to take the queen on e3 with the pawn on d2. In this case, there is only one pawn sacrificed.
A better play is the following:
1. Move the pawn from d2 to d3. Queen captures the pawn on e3.
2. Move the pawn from c2 to c3. Queen captures the pawn on d3.
3. Move the pawn from a2 to a3. Queen captures the pawn on c3.
4. Move the pawn from h4 to h5. Queen captures the pawn on a3.
5. Move the pawn from h5 to h6. The black queen cannot capture this pawn.
Thus, we were able to sacrifice 4 pawns.
But there is an even better alternative:
1. Move the pawn from d2 to d3. Queen captures the pawn on e3.
2. Move the pawn from d3 to d4. Queen captures the pawn on d4.
3. Move the pawn from a2 to a3. Queen captures the pawn on h4.
4. Move the pawn from a3 to a4. Queen captures the pawn on a4.
5. Move the pawn from c2 to c4. Queen captures the pawn on c4.
Now we managed to give away all the pawns, so the correct answer for this example is 5.
|
|
|
| 1) | |
| | | Returns: 0 | | White is forced to capture the queen on g3 with the pawn on h2, so no pawns are being captured. |
|
|
| 2) | |
| | |
| 3) | |
| | | Returns: 1 | | We can only move the pawn from h7 to h8. If the black player captures this pawn, we can sacrifice the pawn on a7 as well. But since their play is optimal, the queen would capture the pawn on a7 and the game ends.
|
|
|
| 4) | |
| | {"a3","b3","c3","d3","e3","f3","g3","h3"} | "d8" |
| Returns: 7 | | An example with the maximum number of pawns on the board. |
|
|