TCS Code Vita Season-5 Round-1 set-2 Program-4

Problem : Knight Moves

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 text line and using only the ASCII character set. A FEN record contains six fields. A complete description of the FEN format to represent Chess positions can be found at 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 w

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 b

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 w
4. rnbqkbnr/pppp1ppp/8/4p3/4PP2/8/PPPP2PP/RNBQKBNR b
5. rnbqkbnr/pppp1ppp/8/8/4Pp2/8/PPPP2PP/RNBQKBNR w

Wikipedia describes first field of FEN format as follows

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.

The second field denotes whose move it is now. “w” depicts that it is White’s turn to play and “b” indicates that it is Black’s turn to play

CodeVita Problem Statement

Given a board position in FEN format, your task is to find out all the move(s) that Knight(s) of the playing side can make.

Input Format:
1.    First line contains single FEN record, which corresponds to a particular board position and also indicates whose turn it is.

Output Format:
1.    The output must be printed as follows
1.    All legal moves that Knight can make must be in the format “[<Move Format>]”
2.    Where <Move Format> is move represented in format “[fromSquare][toSquare]”
2.    See Example section for better understanding of output format
3.    Follow Output printing specification to print the output in required format

Sample Input and Output
 SNo. Input Board Depiction Output 1 3k4/8/8/8/8/1K4R1/5R2/7N w [] 2 3k4/8/8/8/8/6b1/5r2/K6N w [h1g3, h1f2] 3 2k1b3/6n1/n7/5R2/8/8/8/4K3 b [g7e6, g7f5, g7h5, a6b8, a6c7, a6c5, a6b4]
Print Specification: