## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Simplified chess engine

Sharing is caring!

Chess is a very popular game played by hundreds of millions of people. Nowadays, we have chess engines such as Stockfish and Komodo to help us analyze games. These engines are very powerful pieces of well-developed software that use intelligent ideas and algorithms to analyze positions and sequences of moves, as well as find tactical ideas. Consider the following simplified version of chess:

• Board: It’s played on a $4 \times 4$ board between two players named Black and White.

• Pieces and Movement:

• White initially has $w$ pieces and Black initially has $b$ pieces.
• There are no Kings and no Pawns on the board. Each player has exactly one Queen, at most two Rooks, and at most two minor pieces (i.e., a Bishop and/or Knight).
• Each piece’s possible moves are the same as in classical chess, and each move made by any player counts as a single move.
• There is no draw when positions are repeated as there is in classical chess.
• Objective: The goal of the game is to capture the opponent’s Queen without losing your own.

Given $m$ and the layout of pieces for $g$ games of simplified chess, implement a very basic (in comparison to the real ones) engine for our simplified version of chess with the ability to determine whether or not White can win in $\le m$ moves (regardless of how Black plays) if White always moves first. For each game, print YES on a new line if White can win under the specified conditions; otherwise, print NO.

Input Format
The first line contains a single integer, $g$, denoting the number of simplified chess games. The subsequent lines define each game in the following format:

• The first line contains three space-separated integers denoting the respective values of $w$ (the number of White pieces), $b$ (the number of Black pieces), and $m$ (the maximum number of moves we want to know if White can win in).

• The $w + b$ subsequent lines describe each chesspiece in the format t c r, where $t$ is a character $\in \{Q,N,B,R\}$ denoting the type of piece (where $Q$ is Queen, $N$ is Knight, $B$ is Bishop, and $R$ is Rook), and $c$ and $r$ denote the respective column and row on the board where the figure is placed (where $c \in \{A,B,C,D\}$ and $r \in \{1,2,3,4\}$). These inputs are given as follows:

• Each of the $w$ subsequent lines denotes the type and location of a White piece on the board.
• Each of the $b$ subsequent lines denotes the type and location of a Black piece on the board.

Constraints
It is guaranteed that the locations of all pieces given as input are distinct. $1 \le g \le 200$ $1 \le w,b \le 5$ $1 \le m \le 6$
Each player initially has exactly one Queen, at most two Rooks and at most two minor pieces.

Output Format
For each of the $g$ games of simplified chess, print whether or not White can win in $\le m$ moves on a new line. If it’s possible, print YES; otherwise, print NO.

Sample Input 0

1
2 1 1
N B 2
Q B 1
Q A 4


Sample Output 0

YES


Explanation 0
We play $g=1$ games of simplified chess, where the initial piece layout is as follows: White is the next to move, and they can win the game in $1$ move by taking their Knight to $A4$ and capturing Black’s Queen. Because it took $1$ move to win and $1 \le m$, we print YES on a new line.

input 1 expected output 1
input 2 expected output 2

Solution
Just to have an overview of the how the different chess pieces move, I have listed the moves below for quick reference:

Next, we need to figure out a strategy. Since the goal of the game is to capture the opponent’s Queen without losing your own a player can (1) avoid moves that put his Queen in jeopardy and (2) make a move that takes his Queen out of danger if the Queen happens to be in danger.

We are going to solve this problem using recursion. At this point it is worth noting the fact that depending on what player’s turn it is, a winning board has a different outcome depending on the current player. This will be important when handling return values from our recursive function calls. More on that later.

The board will internally be represented using an int[][] board array of size $4 \times 4$. We also need to distinguish the White player pieces from the Black player pieces. I will use odd numbers for the pieces belonging to the White player and even numbers for the pieces belonging to the Black player:

// Odd is White
private static final int QUEEN_W = 1;
private static final int KNIGHT_W = 3;
private static final int BISHOP_W = 5;
private static final int ROOK_W = 7;

// Even is Black
private static final int QUEEN_B = 2;
private static final int KNIGHT_B = 4;
private static final int BISHOP_B = 6;
private static final int ROOK_B = 8;


Next, we are going to store all possible movement directions for each piece in a dedicated array:

private static final int[] queenR = { -1, -1, -1, 0, 0, 1, 1, 1 };
private static final int[] queenC = { -1, 0, 1, -1, 1, -1, 0, 1 };

private static final int[] knightR = { -2, -2, -1, -1, 1, 1, 2, 2 };
private static final int[] knightC = { -1, 1, -2, 2, -2, 2, -1, 1 };

private static final int[] bishopR = { -1, -1, 1, 1 };
private static final int[] bishopC = { -1, 1, -1, 1 };

private static final int[] rookR = { -1, 0, 0, 1 };
private static final int[] rookC = { 0, -1, 1, 0 };


Wer are going to also define some helper functions that will help us determine if a given row and column are within board limits and if a movement to a given square is valid:

private static boolean isWithinLimits(int r, int c) {
return ((r >= 0 && r < ROWS) && (c >= 0 && c < COLUMNS));
}

private static boolean isValid(int[][] board, int r, int c, int player) {
// We are within limits AND (it is empty OR occupied by opponent)
return (isWithinLimits(r, c) && (board[r][c] == EMPTY || (board[r][c] != EMPTY && board[r][c] % 2 != player)));
}


The player parameter in the isValid(...) valid function takes two possible values: 1 when we are calling isValid(...) for the White player and 0 when we are calling isValid(...) for the Black player. isValid(...) returns true if we are within board limits and the square we are planning to move is not occupied by one of our own pieces. It return false otherwise.

Next, we are going to define helper functions, that we can call for a given board to determine if White or Black have won the game. That is, if the opponent does not have a Queen on the board:

private static boolean isWinForPlayer(int[][] board, int player) {
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLUMNS; c++) {
if (board[r][c] == (player == WHITE ? QUEEN_B : QUEEN_W)) {
return false;
}
}
}

return true;
}


player takes two possible values: 1 when we are calling isWinForPlayer(...) for the White player and 0 when we are calling isWinForPlayer(...) for the Black player. It returns true if the player wins and false otherwise.

We also define a function that returns the position of a player's Queen on the board:

private static int[] queen(int[][] board, int player) {
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLUMNS; c++) {
if (board[r][c] != EMPTY && board[r][c] % 2 == player && (board[r][c] == QUEEN_W || board[r][c] == QUEEN_B)) {
return new int[]{r, c};
}
}
}

return new int[]{-1, -1};
}


Next, we need a function that lets us know if the Queen of a player is safe in a given board:

private static boolean isQueenSafeForPlayer(int[][] board, int player) {
int[] queen = queen(board, player);
int qr = queen;
int qc = queen;

if (qr == -1 && qc == -1) {
// Player has no Queen on board --> Lost
return false;
}

if (player == WHITE && isWinForPlayer(board, WHITE)) {
return true;
}

if (player == BLACK && isWinForPlayer(board, BLACK)) {
return true;
}

// Check if opponent's Queen is in the way
for (int dir = 0; dir < queenR.length; dir++) {
LEN: for (int len = 1; len < 4; len++) {
int tr = qr + queenR[dir] * len;
int tc = qc + queenC[dir] * len;

if (isWithinLimits(tr, tc) && (board[tr][tc] % 2 != player) && (board[tr][tc] == QUEEN_B || board[tr][tc] == QUEEN_W)) {
// There is a Queen that does not belong to us
return false;
}

if (isWithinLimits(tr, tc) && board[tr][tc] != EMPTY) {
// A piece is in the way
break LEN;
}
}
}

// Check if opponent's Knight is in the way
for (int dir = 0; dir < knightR.length; dir++) {
int tr = qr + knightR[dir];
int tc = qc + knightC[dir];
if (isWithinLimits(tr, tc) && (board[tr][tc] % 2 != player) && (board[tr][tc] == KNIGHT_B || board[tr][tc] == KNIGHT_W)) {
// There is a Knight that does not belong to us
return false;
}
}

// Check if opponent's Bishop is in the way
for (int dir = 0; dir < bishopR.length; dir++) {
LEN: for (int len = 1; len < 4; len++) {
int tr = qr + bishopR[dir] * len;
int tc = qc + bishopC[dir] * len;
if (isWithinLimits(tr, tc) && (board[tr][tc] % 2 != player) && (board[tr][tc] == BISHOP_B || board[tr][tc] == BISHOP_W)) {
// There is a Bishop that does not belong to us
return false;
}
if (isWithinLimits(tr, tc) && board[tr][tc] != EMPTY) {
// A piece is in the way
break LEN;
}
}
}

// Check if opponent's Rook is in the way
for (int dir = 0; dir < rookR.length; dir++) {
LEN: for (int len = 1; len < 4; len++) {
int tr = qr + rookR[dir] * len;
int tc = qc + rookC[dir] * len;
if (isWithinLimits(tr, tc) && (board[tr][tc] % 2 != player) && (board[tr][tc] == ROOK_B || board[tr][tc] == ROOK_W)) {
// There is a Rook that does not belong to us
return false;
}
if (isWithinLimits(tr, tc) && board[tr][tc] != EMPTY) {
// A piece is in the way
break LEN;
}
}
}

return true;
}


Note above that for Queen, Bishop and Rook we take the movement directions and try them out for lengths $1\dots 4$. This is not the case for a Knight (see Knight movement illustration above) where the movement does not have a variable length. Also notice for Queen, Bishop and Rook, if any piece is in the way we do not need to check the positions beyond that square since it blocks any opponent's piece beyond that point.

Now that we have implemented our helper functions we can proceed with the actual algorithm. We are going to solve this by calling our main function canWhiteWin(int[][] board, int m, int player) recursively. Our exit conditions will be reaching the limit of our allowed number of moves, reaching a state where White wins or reaching a state where Black wins:

private static boolean canWhiteWin(int[][] board, int m, int player) {
if (isWinForPlayer(board, WHITE)) {
return true;
}

if (isWinForPlayer(board, BLACK)) {
return false;
}

if (m <= 0) {
return false;
}

// Try every possible move here
. . .

// Player was not able to make a movement. Checkmate!
if (player == BLACK && m > 1) {
return true;
} else {
return false;
}
}


canWhiteWin(...) is called for every possible positions the player can move a piece and for all the player's pieces on the board. A player recursively calls canWhiteWin(...) only for valid positions and if his Queen is safe in the resulting board. canWhiteWin(...) returns true if White player can win and false otherwise. We need to handle the result after every recursive function call differently depending on the current player. If the current player who called canWhiteWin(...) is White and the resulting value is true we do not need to examine any further positions. We exit by returning true, since White has found a move from the current board state that guaranties a win, no matter how Black plays next. If the current player who called canWhiteWin(...) is Black and the resulting value is false, we exit by returning false since from the current board state Black can make a move that results in White losing.

For Queen, Bishop and Rook we take the movement directions and try them out for lengths $1\dots 4$. This is not the case for a Knight (see Knight movement illustration above) where the movement does not have a variable length. Also notice for Queen, Bishop and Rook, if any piece is in the way we do not need to check the positions beyond that square since it blocks the route to a square beyond that point.

Finally, if White cannot make a move, because his Queen would not be safe we return false. If a Black cannot make a move and $m>1$ we return true since black will be forced to make a move that puts his Queen at risk, which White can take in his next move.

That's it! The full algorithm is listed below.

Full code

public class SimplifiedChessEngine {
private static final int EMPTY = 0;
private static final int ROWS = 4;
private static final int COLUMNS = 4;
private static final int WHITE = 1;
private static final int BLACK = 0;

// Odd is White
private static final int QUEEN_W = 1;
private static final int KNIGHT_W = 3;
private static final int BISHOP_W = 5;
private static final int ROOK_W = 7;

// Even is Black
private static final int QUEEN_B = 2;
private static final int KNIGHT_B = 4;
private static final int BISHOP_B = 6;
private static final int ROOK_B = 8;

// Movements
private static final int[] queenR = { -1, -1, -1, 0, 0, 1, 1, 1 };
private static final int[] queenC = { -1, 0, 1, -1, 1, -1, 0, 1 };

private static final int[] knightR = { -2, -2, -1, -1, 1, 1, 2, 2 };
private static final int[] knightC = { -1, 1, -2, 2, -2, 2, -1, 1 };

private static final int[] bishopR = { -1, -1, 1, 1 };
private static final int[] bishopC = { -1, 1, -1, 1 };

private static final int[] rookR = { -1, 0, 0, 1 };
private static final int[] rookC = { 0, -1, 1, 0 };

private static int characterW2Int(char t) {
switch (t) {
case 'Q':
return QUEEN_W;
case 'N':
return KNIGHT_W;
case 'B':
return BISHOP_W;
default:
return ROOK_W;
}
}

private static int characterB2Int(char t) {
switch (t) {
case 'Q':
return QUEEN_B;
case 'N':
return KNIGHT_B;
case 'B':
return BISHOP_B;
default:
return ROOK_B;
}
}

private static void move(int[][] board, int sr, int sc, int tr, int tc) {
board[tr][tc] = board[sr][sc];
board[sr][sc] = EMPTY;
}

private static boolean isWithinLimits(int r, int c) {
// we are within limits
return ((r >= 0 && r < ROWS) && (c >= 0 && c < COLUMNS));
}

private static boolean isValid(int[][] board, int r, int c, int player) {
// we are within limits AND (it is empty OR occupied by opponent)
return (isWithinLimits(r, c) && (board[r][c] == EMPTY || (board[r][c] != EMPTY && board[r][c] % 2 != player)));
}

private static boolean isWinForPlayer(int[][] board, int player) {
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLUMNS; c++) {
if (board[r][c] == (player == WHITE ? QUEEN_B : QUEEN_W)) {
return false;
}
}
}

return true;
}

private static int[] queen(int[][] board, int player) {
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLUMNS; c++) {
if (board[r][c] != EMPTY && board[r][c] % 2 == player && (board[r][c] == QUEEN_W || board[r][c] == QUEEN_B)) {
return new int[] { r, c };
}
}
}

return new int[] { -1, -1 };
}

private static boolean isQueenSafeForPlayer(int[][] board, int player) {
int[] queen = queen(board, player);
int qr = queen;
int qc = queen;

if (qr == -1 && qc == -1) {
// Player has no Queen on board --> Lost
return false;
}

if (player == WHITE && isWinForPlayer(board, WHITE)) {
return true;
}

if (player == BLACK && isWinForPlayer(board, BLACK)) {
return true;
}

// Check if opponent's Queen is in the way
for (int dir = 0; dir < queenR.length; dir++) {
LEN: for (int len = 1; len < 4; len++) {
int tr = qr + queenR[dir] * len;
int tc = qc + queenC[dir] * len;

if (isWithinLimits(tr, tc) && (board[tr][tc] % 2 != player) && (board[tr][tc] == QUEEN_B || board[tr][tc] == QUEEN_W)) {
// There is a Queen that does not belong to us
return false;
}

if (isWithinLimits(tr, tc) && board[tr][tc] != EMPTY) {
// A piece is in the way
break LEN;
}
}
}

// Check if opponent's Knight is in the way
for (int dir = 0; dir < knightR.length; dir++) {
int tr = qr + knightR[dir];
int tc = qc + knightC[dir];
if (isWithinLimits(tr, tc) && (board[tr][tc] % 2 != player) && (board[tr][tc] == KNIGHT_B || board[tr][tc] == KNIGHT_W)) {
// There is a Knight that does not belong to us
return false;
}
}

// Check if opponent's Bishop is in the way
for (int dir = 0; dir < bishopR.length; dir++) {
LEN: for (int len = 1; len < 4; len++) {
int tr = qr + bishopR[dir] * len;
int tc = qc + bishopC[dir] * len;
if (isWithinLimits(tr, tc) && (board[tr][tc] % 2 != player) && (board[tr][tc] == BISHOP_B || board[tr][tc] == BISHOP_W)) {
// There is a Bishop that does not belong to us
return false;
}
if (isWithinLimits(tr, tc) && board[tr][tc] != EMPTY) {
// A piece is in the way
break LEN;
}
}
}

// Check if opponent's Rook is in the way
for (int dir = 0; dir < rookR.length; dir++) {
LEN: for (int len = 1; len < 4; len++) {
int tr = qr + rookR[dir] * len;
int tc = qc + rookC[dir] * len;
if (isWithinLimits(tr, tc) && (board[tr][tc] % 2 != player) && (board[tr][tc] == ROOK_B || board[tr][tc] == ROOK_W)) {
// There is a Rook that does not belong to us
return false;
}
if (isWithinLimits(tr, tc) && board[tr][tc] != EMPTY) {
// A piece is in the way
break LEN;
}
}
}

return true;
}

private static boolean canWhiteWin(int[][] board, int m, int player) {
if (isWinForPlayer(board, WHITE)) {
return true;
}

if (isWinForPlayer(board, BLACK)) {
return false;
}

if (m <= 0) {
return false;
}

for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLUMNS; c++) {
if (board[r][c] != EMPTY && board[r][c] % 2 == player) {

if ((player == WHITE && board[r][c] == QUEEN_W) || (player == BLACK && board[r][c] == QUEEN_B)) {
for (int dir = 0; dir < queenR.length; dir++) {
LEN: for (int len = 1; len < 4; len++) {
int tr = r + queenR[dir] * len;
int tc = c + queenC[dir] * len;

if (isValid(board, tr, tc, player)) {
int tmp = board[tr][tc];
move(board, r, c, tr, tc);

if (isQueenSafeForPlayer(board, player)) {
// Recursive call
if (player == WHITE) {
if (canWhiteWin(board, m - 1, player == WHITE ? BLACK : WHITE)) {
// Move back
move(board, tr, tc, r, c);
board[tr][tc] = tmp;

return true;
}
} else {
if (!canWhiteWin(board, m - 1, player == WHITE ? BLACK : WHITE)) {
// Move back
move(board, tr, tc, r, c);
board[tr][tc] = tmp;

return false;
}
}
}

// Move back
move(board, tr, tc, r, c);
board[tr][tc] = tmp;

}

if (isWithinLimits(tr, tc) && board[tr][tc] != EMPTY) {
// A piece is in the way
break LEN;
}
}
}
}

if ((player == WHITE && board[r][c] == KNIGHT_W) || (player == BLACK && board[r][c] == KNIGHT_B)) {
for (int dir = 0; dir < knightR.length; dir++) {
int tr = r + knightR[dir];
int tc = c + knightC[dir];

if (isValid(board, tr, tc, player)) {
int tmp = board[tr][tc];
move(board, r, c, tr, tc);

if (isQueenSafeForPlayer(board, player)) {
// Recursive call
if (player == WHITE) {
if (canWhiteWin(board, m - 1, player == WHITE ? BLACK : WHITE)) {
// Move back
move(board, tr, tc, r, c);
board[tr][tc] = tmp;

return true;
}
} else {
if (!canWhiteWin(board, m - 1, player == WHITE ? BLACK : WHITE)) {
// Move back
move(board, tr, tc, r, c);
board[tr][tc] = tmp;

return false;
}
}
}

// Move back
move(board, tr, tc, r, c);
board[tr][tc] = tmp;
}
}
}

if ((player == WHITE && board[r][c] == BISHOP_W) || (player == BLACK && board[r][c] == BISHOP_B)) {
for (int dir = 0; dir < bishopR.length; dir++) {
LEN: for (int len = 1; len < 4; len++) {
int tr = r + bishopR[dir] * len;
int tc = c + bishopC[dir] * len;

if (isValid(board, tr, tc, player)) {
int tmp = board[tr][tc];
move(board, r, c, tr, tc);

if (isQueenSafeForPlayer(board, player)) {
// Recursive call
if (player == WHITE) {
if (canWhiteWin(board, m - 1, player == WHITE ? BLACK : WHITE)) {
// Move back
move(board, tr, tc, r, c);
board[tr][tc] = tmp;

return true;
}
} else {
if (!canWhiteWin(board, m - 1, player == WHITE ? BLACK : WHITE)) {
// Move back
move(board, tr, tc, r, c);
board[tr][tc] = tmp;

return false;
}
}
}

// Move back
move(board, tr, tc, r, c);
board[tr][tc] = tmp;
}

if (isWithinLimits(tr, tc) && board[tr][tc] != EMPTY) {
// A piece is in the way
break LEN;
}
}
}
}

if ((player == WHITE && board[r][c] == ROOK_W) || (player == BLACK && board[r][c] == ROOK_B)) {
for (int dir = 0; dir < rookR.length; dir++) {
LEN: for (int len = 1; len < 4; len++) {
int tr = r + rookR[dir] * len;
int tc = c + rookC[dir] * len;

if (isValid(board, tr, tc, player)) {
int tmp = board[tr][tc];
move(board, r, c, tr, tc);

if (isQueenSafeForPlayer(board, player)) {
// Recursive call
if (player == WHITE) {
if (canWhiteWin(board, m - 1, player == WHITE ? BLACK : WHITE)) {
// Move back
move(board, tr, tc, r, c);
board[tr][tc] = tmp;

return true;
}
} else {
if (!canWhiteWin(board, m - 1, player == WHITE ? BLACK : WHITE)) {
// Move back
move(board, tr, tc, r, c);
board[tr][tc] = tmp;

return false;
}
}
}

// Move back
move(board, tr, tc, r, c);
board[tr][tc] = tmp;
}

if (isWithinLimits(tr, tc) && board[tr][tc] != EMPTY) {
// A piece is in the way
break LEN;
}
}
}
}

}
}
}

// Player was not able to make a movement. Checkmate!
if (player == BLACK && m > 1) {
return true;
} else {
return false;
}
}

public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
Scanner in = new Scanner(System.in);

int games = in.nextInt();
for (int g = 0; g < games; g++) {
int[][] board = new int[ROWS][COLUMNS];

int w = in.nextInt();
int b = in.nextInt();
int m = in.nextInt();

for (int i = 0; i < w; i++) {
char t = in.next().charAt(0);
char c = in.next().charAt(0);
int r = in.nextInt();
board[4 - r][c - 'A'] = characterW2Int(t);
}

for (int i = 0; i < b; i++) {
char t = in.next().charAt(0);
char c = in.next().charAt(0);
int r = in.nextInt();
board[4 - r][c - 'A'] = characterB2Int(t);
}

// Call algorithm
boolean win = canWhiteWin(board, m, WHITE);
String result = win ? "YES" : "NO";
System.out.println(result);
}

}
}