Programming Geek
Rated 4.7/5 based on 1446 reviews

### CodeVita 2016 Round 2 Question: Mate In Two

Problem : Mate In Two

Background

A Chess board position is accurately captured by Forsyth-Edwards notation and is abbreviated as FEN. A FEN "record" defines a particular game position, all in one line of text and using only the ASCII character set. A FEN record consists of six fields. A complete description of the FEN format to represent Chess positions can be found here

For the purpose of this problem, only consider first of the six fields of FEN. Before we describe the problem, let us look at how FEN maps to a board position. The following 5 images show board positions and its corresponding FEN representation.

Figure 1.

 This board position depicts initial position before any side has made a move. In FEN format this board position is represented as rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR

Let's say, White plays e4. Then the board position looks like shown below

Figure 2.

 This board position depicts the Chess board after White has played e4. In FEN format this board position is represented as rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR

Similarly, 3 more half-moves are depicted in following diagrams

 Figure 3. Figure 4. Figure 5.

The FENs corresponding to Figure 3, 4 and 5 are represented as

3. rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR
4. rnbqkbnr/pppp1ppp/8/4p3/4PP2/8/PPPP2PP/RNBQKBNR
5. rnbqkbnr/pppp1ppp/8/8/4Pp2/8/PPPP2PP/RNBQKBNR

Wikipedia describes first field of FEN format as follows

Piece placement (from white's perspective). Each rank is described, starting with rank 8 and ending with rank 1; within each rank, the contents of each square are described from file "a" through file "h". Following the Standard Algebraic Notation (SAN), each piece is identified by a single letter taken from the standard English names (pawn = "P", knight = "N", bishop = "B", rook = "R", queen = "Q" and king = "K").[1] White pieces are designated using upper-case letters ("PNBRQK") while black pieces use lowercase ("pnbrqk"). Empty squares are noted using digits 1 through 8 (the number of empty squares), and "/" separates ranks

Statement

Given a board position in FEN format, your task is to find out all move(s) that lead to a forced mate. White to play and win in 2 moves.

Input Format:
1. First line contains single FEN record, which corresponds to a particular board position

Output Format:
1. The output must be printed as follows
1. A string in format by "< move format >-< move format >-< move format >", where first move is white move, second is black move and third is again a white move
2. Where < move format > is move represented in format "fromSquaretoSquare"
2. See Example section for better understanding of output format

Constraints:
1. The board position will always be White to move and mate in 2
2. Since we focus on only first part of the FEN, we are essentially ignoring possibility of Castling being a mating move. Hence our test cases don't contain FENs which give rise to such positions.
3. There is no need to handle En Passant positions. There are no test cases involving En Passant moves.
4. No need to implement pawn promotion rules. Our test cases do not contain positions which will lead to a pawn getting promoted and inflicting a mate.
5. There is exactly one forced mating sequence in our test cases. So once a forced mating sequence is found, there is no need to process further.

Sample Input and Output

SNo.InputOutput
1
r1b2rk1/1p4pR/p2pppn1/6q1/3NP1P1/2N2P2/PPP4Q/1K5R

h7g7-g8g7-h2h7
2
5r1k/p4p1p/5P1N/1p1p4/2pP3P/8/PP4RK/8

g2g8-f8g8-h6f7

Explanation:

 Board position for sample input 1:                      Figure 6. Mate enforcing moves for input 1:                      Figure 7. Board position for sample input 2:                                                Figure 8. Mate enforcing moves for input 2:                      Figure 9.