AAA-Valid Moves Generation Solved

Update to Assignment
Since there is not much time left, we will be simplifying the game slightly. In particular, you may ignore crocodiles, monkeys and giraffes and superpawns going forward. This does not apply to part 1, so please complete that assuming that these pieces may exist. From now on, you may assume that the game starts with none of these pieces on the board. If a pawn reaches the end rank, it does not get promoted to a superpawn. The new starting position will be

Z0
 Z Z
 0Z
po
pop
op
Z0
Z0Z
0Z
0Z
0Z0
Z0
Z0
Z0Z
0Z
PO
POP
OP
Z0
 Z Z
 0Z
7

6

5

4

3

2

1

                                                                                a       b       c       d       e       f       g

Figure 1: The starting position for White and Black excluding giraffes, monkeys and crocodiles.

       1       Introduction
In this section, we will need to generate the valid moves available to a player given the current state of the game. We will need to write code that accepts a game state as a FEN string and sets up the board (see Part 1 if you have no already done so). Once this has been done, the next step is to generate the moves available at the current position. This will depend on whether it is white or black to play.

       2       Move Representations
For every submission, we will represent a move as a string <start_square><end_square> specifying the starting location of the piece to move and then square the piece ends up on. For example, the move e3e4 represents a piece moving from e3 to e4.

       3       Input Hint
Hint: a reminder not to be careful when mixing cin with getline. An example of doing so is below:

int N; cin >> N; cin.ignore(); //NB!

for (int i = 0; i < N; ++i) { string fen; getline(cin, fen);

}
1

2

3

4

5

6

7


Submission 1: Generate Lion Moves
Write a C++ program that accepts a FEN string, stores the piece location information in appropriate data structures, and then outputs the valid lion moves that can be made by whichever player it is to move. As a reminder, the lion moves as follows:

Lion: The lion moves and captures one square in any direction (including diagonally), but it may not leave its 3×3 castle (highlighted in brown in the diagrams). However, there is one exception to this rule: a lion is allowed to move in a straight or diagonal line across the river if it is able to immediately capture the opposing lion. If a player’s lion is captured, that player immediately loses the game. The diagram below shows the moves the white lion is able to make.

Z0
 Z0Z
0Z
0Z
pZ0
Z0
Z0
Z0Z
0Z
0Z0Z0Z0
 Z0Z0Z0Z

0Z0o0Z0

Z0Z0Z0Z
 7 Z0Z0Z0Z 7 6 0Z0Z0Z0 6 5 Z0Z0Z0Z 5 4 0Z0Z0Z0 4 3 Z0Z0Z0Z 3 2 0Z0o0Z0 2 1 Z0Z0Z0Z

1 a                                                                                                   b   c              d              e              f               g

            a       b       c       d      e       f       g
 
(a) In the current position, White’s lion on c3 can move to the squares marked by a red square or can capture Black’s pawn on d2 (red circle).
(b) Compared to the position on the left, the White lion on c3 can now also move across the river to capture the Black lion on e5 and win the game (red arrow)! The White lion could also potentially capture Black’s lion anywhere along the c-file.
Input
The first line of input is N, the number of FEN strings that must be read in as input. N lines follow, with each line consisting of a single FEN string. You may assume that each FEN string is a valid position, and so will contain exactly one white lion and one black lion.

Output
For each FEN string i, output the valid lion moves. The moves should be printed in alphabetical order, and should be separated by a single space. Each move should be printed using the encoding described in Section 2. If there are no valid moves, nothing should be printed.

2ele1z/ppppppp/7/7/7/PPP1PPP/2ELE1Z w 4

1e1El2/P1P2P1/1P5/7/1E3P1/1P5/4L2 b 79

Sample Output
d1d2 e7d6 e7d7 e7e1 e7e6

Visualisation of Above Test Cases
Z0
 Z Z
 0Z
po
pop
op
Z0
Z0Z
0Z
0Z
0Z0
Z0
Z0
Z0Z
0Z
PO
PZP
OP
Z0
 Z Z
 0Z
7

6

5

4

3

2

1

                   a       b       c       d       e       f       g

(a)            The White lion can only move to d2, sinceit is blocked by its other pieces.

Z 
 Z Z
0Z
PZ
PZ0
O0
ZP
Z0Z
0Z
0Z
0Z0
Z0
Z 
Z0Z
PZ
0O
0Z0
Z0
Z0
 Z0Z
0Z
7

6

5

4

3

2

1

            a       b       c       d      e       f       g

(b)            The Black lion can move to the emptysquares on d6 and e6 and can capture on d7. It cannot move to f7 or f6, since that would be outside of its 3×3 castle. It can also fly across the river to capture the white lion on e1.

Submission 2: Generate Zebra Moves
Write a C++ program that accepts a FEN string, stores the piece location information in appropriate data structures, and then outputs the valid zebra moves that can be made by whichever player it is to move. As a reminder, the zebra moves two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an L). The zebra can jump over pieces to reach its destination.

 Z0Z0Z0Z 0Z0Z0Z0 opZ0Z Z
0ZpZ0Z0
OP
Z0Z
PZ
0Z
0Z 
Z0
Z0
 Z0Z
0Z
 7 Z0Z0Z0Z 7 6 0Z0Z0Z0     6 5 opZ0Z Z       5 4 0ZpZ0Z0     4 3 OPZ0ZPZ  3 2 0Z0Z Z0       2 1 Z0Z0Z0Z     1
                   a       b       c       d       e       f       g                                         a       b      c       d      e       f       g

(a) The White zebra on e2 can move to any (b) The Black zebra can move to any square square indicated by the arrows. It cannot move indicated by the arrows and can thus choose to c1, since that square is occupied by another to capture the White piece on f5. White piece. Note that the pawn on f3 does not prevent the zebra from jumping to f4 or g3.

Input
The first line of input is N, the number of FEN strings that must be read in as input. N lines follow, with each line consisting of a single FEN string. The FEN string may contain 0 or 1 Black and White zebras.

Output
For each FEN string i, output the valid zebra moves. The moves should be printed in alphabetical order, and should be separated by a single space. Each move should be printed using the encoding described in Section 2. If there are no valid moves, or no zebras for the side to move exist, nothing should be printed.

6E/3pl1p/ezZ4/E6/2L4/3p3/7 w 45

7/7/2lP1p1/7/2ppeE1/1z4P/4L2 b 32

Sample Output
c5a6 c5b3 c5b7 c5d3 c5d7 c5e4 c5e6 b2a4 b2c4 b2d1

Visualisation of Above Test Cases
Z0
Z0Z
 0Z
0Z
0o 
Zp
 Z
 Z0Z
0Z
 Z
0Z0
Z0
Z0
 Z0Z
0Z
0Z
0o0
Z0
Z0
Z0Z
0Z
7

6

5

4

3

2

1

                   a       b       c       d       e       f       g

(a)            The White zebra can move to empty squares on a6,b3,b7,d3,d7 and e4. It can also capture the Black lion on e6. It cannot move to a4, since it is occupied by a white piece.

Z0
Z0Z
0Z
0Z
0Z0
Z0
Z0
 ZPZ
pZ
0Z
0Z0
Z0
Z0
 opZ
 Z
 0Z
0Z0
ZP
Z0
 Z0Z
0Z
7

6

5

4

3

2

1

            a       b       c       d      e       f       g

(b)            The Black zebra can move to empty squareson a4, c4 and d1. It cannot move to d3, since it is occupied by a black piece.

Submission 3: Generate Elephant Moves

Write a C++ program that accepts a FEN string, stores the piece location information in appropriate data structures, and then outputs the valid elephant moves that can be made by whichever player it is to move. As a reminder, the elephant can move or capture one or two squares horizontally or vertically in any direction. If it moves two squares, this move is a jump. Therefore, if there is any piece in the way, it does not block the elephant from moving
two squares.

 7 Z0Z0Z0Z 6 0Z0Z0Z0 5 Z0Z0Z0Z 4 0ZpZ0Z0 3 OPZ0ZPZ 2 0Z0Z Zp 1 Z0Z0Z0Z
                   a       b       c       d       e       f       g

(a) The White elephant on e2 can move to any of the squares marked by a red square, and it can capture the Black piece in g2 (circled in red). Note that it cannot move to d2 since another White piece occupies that square, but it can jump to c2 (and is not blocked by the piece on d2).

Input

 7 Z0Z0Z0Z 6 0Z0Z0Z0 5 Z0Z0Z0Z 4 0Z0Z Z0 3 OPZ0ZPZ 2 0Z0Z0Zp 1 Z0Z0Z0Z
            a       b       c       d      e       f       g

(b) The White elephant on e3 can move to any of the squares marked by a red square. In addition, it can move one square forward to capture the Black piece on e4, (circled in red), or jump two steps to capture the piece on e5 (in this case, the piece on e4 would remain unaffected).

The first line of input is N, the number of FEN strings that must be read in as input. N lines follow, with each line consisting of a single FEN string. The FEN string may contain 0, 1 or 2 Black and White elephants.

Output
For each FEN string i, output the valid elephant moves. The moves should be printed in alphabetical order, and should be separated by a single space. Each move should be printed using the encoding described in Section 2. If there are no valid moves, or no elephant for the side to move exist, nothing should be printed.

4E2/1pl3p/1p2pEP/4P1p/1PPL1ZP/p2pPPz/7 w 40

1z5/pPp1lP1/5ep/4P1e/4L1p/2p2pP/7 b 35

Sample Output
e7c7 e7d7 e7e5 e7e6 e7f7 e7g7 f5d5 f5e5 f5f4 f5f6 f5f7 f5d5 f5e5 f5f3 f5f4 f5f6 f5f7 g4e4 g4f4 g4g2 g4g6

Visualisation of Above Test Cases
Z0
 Z0Z
0Z
0o
 Z0
Zp
Zp
Z0o
 O
0Z
0ZP
Zp
ZP
O Z
 O
pZ
0oP
O 
Z0
Z0Z
0Z
7

6

5

4

3

2

1

                   a       b       c       d       e       f       g

(a)            There are two White elephants, so we must generate moves that start at two different squares. For each starting square, the elephants can move one or two squares vertically or horizontally, unless the square it would land on is occupied by a White piece.

Z 
Z0Z
0Z
pO
pZ 
O0
Z0
Z0Z
 o
0Z
0ZP
Z 
Z0
 Z0Z
0o
0Z
pZ0
oP
Z0
Z0Z
0Z
7

6

5

4

3

2

1

a          b     c              d              e              f               g

(b)            There are two Black elephants, so we must generate moves that start at two different squares. For each starting square, the elephants can move one or two squares vertically or horizontally, unless the square it would land on is occupied by a Black piece.

Submission 4: Generate Pawn Moves

Write a C++ program that accepts a FEN string, stores the piece location information in appropriate data structures, and then outputs the valid pawn moves that can be made by whichever player it is to move. As a reminder, a pawn can move and capture one step straight or diagonally forward. (Black pawns move forward towards rank 1, while White pawns move forward towards the rank 7.) When past the river, it can move (but not capture) one or two steps straight backwards. However, this is not a jumping move, and so the pawn may not move backwards if there is a piece in its path.

Since we are implementing a simplified version of the game, when a pawn reaches the opposite end of the board, no promotion takes place, and its only moves are to retreat.

Z0
Z Z
0Z
0Z
 0Z0
Z0
ZP
Z0Z
0Z
 0Z
0Z0
Z0
 Z0
Z Z
0Z
0Z
0Z0
Z0
Z0
Z0Z
0Z
7 Z0Z0Z0Z                                  7

6 0Z0Z0o0                                 6

5 Z0Z0Z Z                                   5

4 0O0Z0Z0                                 4

 3 Z0Z Z0Z                                   3

2 0Z0Z0Z0                                  2

1 Z0Z0Z0Z                                  1
a          b     c              d              e              f               g

(a)            In this position, neither pawn has managedto cross the river completely yet. The White pawn on b4 can therefore only advance onto any square indicated by a red square, while the Black pawn on f6 can only advance to any square indicated by a green square or capture the White piece on f5 (green circle).

            a       b       c       d      e       f       g

(b)            The White pawn on b5 has crossed theriver and so now can retreat one or two squares straight backwards (indicated by red circles) in addition to advancing forward (red squares).

Input
The first line of input is N, the number of FEN strings that must be read in as input. N lines follow, with each line consisting of a single FEN string.

Output
For each FEN string i, output the valid pawn moves. The moves should be printed in alphabetical order, and should be separated by a single space. Each move should be printed using the

encoding described in Section 2. If there are no valid moves, or no pawns for the side to move

exist, nothing should be printed.

Example Input-Output

Sample Input
2

3l3/7/6P/7/1Z1P1p1/3L3/7 w 23

3l3/p6/7/7/1Z1P1p1/3L3/1p5 b 42

Sample Output
d3c4 d3d4 d3e4 g5f6 g5g3 g5g4 g5g6 a6a5 a6b5 b1b2 f3e2 f3f2 f3f4 f3f5 f3g2

Visualisation of Above Test Cases
Z0
Z Z
0Z
0Z
0Z0
Z0
Z0
Z0Z
0O
0Z
0Z0
Z0
Z 
ZPZ
pZ
0Z
 0Z0
Z0
Z0
Z0Z
0Z
7

6

5

4

3

2

1

                   a       b       c       d       e       f       g

(a)            The White pawn on d3 can move to thethree squares in front of it. The pawn on g5 can move to the two square in front, and can also retreat to either g4 or g2, since it is beyond the river.

Z0
Z Z
0Z
pZ
0Z0
Z0
Z0
Z0Z
0Z
0Z
0Z0
Z0
Z 
ZPZ
pZ
0Z
 0Z0
Z0
Zp
Z0Z
0Z
7

6

5

4

3

2

1

            a       b       c       d      e       f       g

(b)            The Black pawn on a6 can move forward toa5 or b5. The pawn on b1 can only retreat one square to b2 (it is blocked from retreated to b3 by the White zebra). The pawn on f3 can move forward to e2, f2 or g2 and can also retreat to either f4 or f5.