# Simplified Chess Engine II

### Problem Statement :

```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 to find tactical ideas. Consider the following simplified version of chess:

Board:
It's played on a  board between two players named Black and White.
Rows are numbered from  to , where the top row is  and the bottom row is .
Columns are lettered from  to , where the leftmost column is  and the rightmost column is .
Pieces and Movement:
White initially has  pieces and Black initially has  pieces.
There are no Kings on the board. Each player initially has exactly  Queen, at most  Pawns, at most  Rooks, and at most  minor pieces (i.e., a Bishop and/or Knight).
White's Pawns move up the board, while Black's Pawns move down the board.
Each move made by any player counts as a single move.
Each piece's possible moves are the same as in classical chess, with the following exceptions:
Pawns cannot move two squares forward.
The en passant move is not possible.
Promotion:
Pawns promote to either a Bishop, Knight, or Rook when they reach the back row (promotion to a Queen is not allowed).
The players must perform promotions whenever possible. This means White must promote their Pawns when they reach any cell in the top row, and Black must promote their Pawns when they reach any cell in the bottom row.
Objective:
The goal of the game is to capture the opponent’s Queen without losing your own.
There will never be a draw or tie scenario like you might see in classical chess.
Given  and the layout of pieces for  games, implement a very basic engine for our simplified version of chess that determines whether or not White can win in  moves (regardless of how Black plays) if White always moves first. For each game, print YES on a new line if White can win in  moves; otherwise, print NO.

Input Format

The first line contains an integer, , denoting the number of games. The subsequent lines describe each game in the following format:

The first line contains three space-separated integers describing the respective values of  (the number of white pieces),  (the number of black pieces), and  (the maximum number of moves we want to know if White can win in).
The  subsequent lines describe each chess piece in the form t c r, where  is a character  denoting the type of piece (where  is Queen,  is Knight,  is Bishop,  is Rook, and  is a Pawn), and  and  denote the respective column and row on the board where the figure is located (where  and ). These inputs are given as follows:
Each of the first  lines describes the type and location of a White piece.
Each of the subsequent  lines describes the type and location of a Black piece.

Output Format

For each of the  games of simplified chess, print whether or not White can win in  moves on a new line. If it's possible, print YES; otherwise, print NO instead.```

### Solution :

```                            ```Solution in C :

In  C :

#include <stdio.h>
#include <string.h>

#define QUEEN   1
#define KNIGHT  2
#define BISHOP  3
#define ROOK    4
#define PAWN    5

#define BOUND   8

int m;
unsigned char __board[8][8];
unsigned char *_board[8]={__board[0]+2, __board[1]+2, __board[2]+2, __board[3]+2,
__board[4]+2, __board[5]+2, __board[6]+2, __board[7]+2};
unsigned char **board=_board+2;

unsigned char black[4][4];

int pl[2]={1, -1};

int moves[6][10][3]={
{},
{ {-1, -1, 3}, {-1, 0}, {-1, 1},
{0, -1}, /*QUEEN*/ {0, 1},
{1, -1},  {1, 0},  {1, 1} },
{ {-2, -1, 1},       {-2, 1},
{-1, -2},          {-1, 2},
/*KNIGHT*/
{1, -2},           {1, 2},
{2, -1},           {2, 1} },
{ {-1, -1, 3},       {-1, 1},
/*BISHOP*/
{1, -1},           {1, 1} },
{           {-1, 0, 3},
{0, -1}, /*ROOK*/  {0, 1},
{1, 0} },
{ {-1, 0, 1}, {-1, -1}, {-1, 1}, /* white */
{0, 0},  /*PAWN*/
{1, 0},   {1, 1}, {1, -1} } /* for black */
};

static int min(int a, int b) {
return a<b?a:b;
}

static int max(int a, int b) {
return a>b?a:b;
}

void init_game(void) {
int i, j;
for (i=0; i<8; i++)
for (j=0; j<8; j++)
__board[i][j]=(BOUND+1)*(!(1<i && i<6 && 1<j && j<6));
memset(black, 0, sizeof(black));
}

void print_board(void) {
int i, j;
char fc[6]={'=', 'Q', 'N', 'B', 'R', 'P'};
for (i=0; i<4; i++, printf("\n"))
for (j=0; j<4; j++)
printf("%c ", fc[board[i][j]]+('a'-'A')*black[i][j]);
printf("\n");
}

int solve(int mv) {
int i, j, k, d, b=mv&1;
int ni, nj, t, tb, r, mm=pl[!b], prom[5]={0, 0, 0, 0, 0}, p;
for (i=0; i<4; i++) {
for (j=0; j<4; j++) {
if (board[i][j] && black[i][j]==b) {
for (k=0; moves[board[i][j]][k][0] || moves[board[i][j]][k][1]; k++) {
for (d=1; d<=moves[board[i][j]][0][2]; d++) {
if (board[i][j]!=PAWN || k) {
if (board[i][j]==PAWN)
t=board[ni=(i+moves[board[i][j]][k+b*4][0])][nj=(j+moves[board[i][j]][k+b*4][1])];
else
t=board[ni=(i+moves[board[i][j]][k][0]*d)][nj=(j+moves[board[i][j]][k][1]*d)];
if (t) {
if (t>BOUND)
break;
else if (t==QUEEN && black[ni][nj]!=b)
return pl[b];
break;
}
}
}
}
}
}
}
if ((mv+1)==m)
return 0;
for (i=0; i<4; i++) {
for (j=0; j<4; j++) {
if (board[i][j] && black[i][j]==b) {
for (k=0; moves[board[i][j]][k][0] || moves[board[i][j]][k][1]; k++) {
for (d=1, t=0; d<=moves[board[i][j]][0][2] && !t; d++) {
prom[0]=board[i][j]; prom[1]=board[i][j]; prom[2]=0;
if (board[i][j]==PAWN) {
t=board[ni=(i+moves[board[i][j]][k+b*4][0])][nj=(j+moves[board[i][j]][k+b*4][1])];
if (k) {
if (t==0 || t>BOUND || black[ni][nj]==b)
break;
} else if (t)
break;
if ((ni==0 && !b) || (ni==3 && b)) {
prom[1]=KNIGHT; prom[2]=BISHOP; prom[3]=ROOK; prom[4]=0;
}
} else {
t=board[ni=(i+moves[board[i][j]][k][0]*d)][nj=(j+moves[board[i][j]][k][1]*d)];
if (t>BOUND || (t && black[ni][nj]==b))
break;
}
for (p=1; prom[p]; p++) {
tb=black[ni][nj];
board[ni][nj]=prom[p];
black[ni][nj]=b;
board[i][j]=0;
black[i][j]=0;
r=solve(mv+1);
board[i][j]=prom[0];
board[ni][nj]=t;
black[i][j]=b;
black[ni][nj]=tb;
if (r==pl[b])
return r;
else if (b)
mm=min(mm, r);
else
mm=max(mm, r);
}
}
}
}
}
}
return mm;
}

int main(void) {
int i, j, g, r, b, w;
char figuremap[26]={['Q'-'A']=QUEEN, ['N'-'A']=KNIGHT, ['B'-'A']=BISHOP,
['R'-'A']=ROOK, ['P'-'A']=PAWN};
char t, c;
scanf("%d", &g);
for (i=0; i<g; i++) {
init_game();
scanf("%d%d%d\n", &w, &b, &m);
for (j=0; j<w; j++) {
scanf("%c %c %d\n", &t, &c, &r);
board[4-r][c-'A']=figuremap[t-'A'];
}
for (j=0; j<b; j++) {
scanf("%c %c %d\n", &t, &c, &r);
r=4-r; c-='A';
board[r][c]=figuremap[t-'A'];
black[r][c]=1;
}
printf("%s\n", solve(0)==1?"YES":"NO");
}

return 0;
}```
```

```                        ```Solution in C++ :

In  C ++  :

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
string pieces = "QNBRP";
int ndx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int ndy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
int pawn[] = {1, -1};
int dx[] = {-1, 0, 0, 1, -1, -1, 1, 1};
int dy[] = {0, -1, 1, 0, -1, 1, -1, 1};

int sq(int x) { return x * x; }

bool f(const vvpii &grid, vi xpos, vi ypos, int turn, int moves){
if (moves == 0) return true;

// can capture queen
for (int i = 0; i < 4; i++){
for (int j = 0; j < 4; j++){
pii p = grid[i][j];
if (p.X != turn) continue;
if (p.Y == 0) {
for (int k = 0; k < 8; k++){
int i2 = i + dx[k], j2 = j + dy[k];
while (i2 >= 0 && i2 < 4 && j2 >= 0 && j2 < 4) {
if (i2 == xpos[1-turn] && j2 == ypos[1-turn]) return true;
if (grid[i2][j2].X != -1) break;
i2 += dx[k]; j2 += dy[k];
}
}
} else if (p.Y == 1) {
if (sq(i - xpos[1-turn]) + sq(j - ypos[1-turn]) == 5) return true;
} else if (p.Y == 2) {
for (int k = 4; k < 8; k++){
int i2 = i + dx[k], j2 = j + dy[k];
while (i2 >= 0 && i2 < 4 && j2 >= 0 && j2 < 4) {
if (i2 == xpos[1-turn] && j2 == ypos[1-turn]) return true;
if (grid[i2][j2].X != -1) break;
i2 += dx[k]; j2 += dy[k];
}
}
} else if (p.Y == 3) {
for (int k = 0; k < 4; k++){
int i2 = i + dx[k], j2 = j + dy[k];
while (i2 >= 0 && i2 < 4 && j2 >= 0 && j2 < 4) {
if (i2 == xpos[1-turn] && j2 == ypos[1-turn]) return true;
if (grid[i2][j2].X != -1) break;
i2 += dx[k]; j2 += dy[k];
}
}
} else {
if (i + pawn[turn] == xpos[1-turn] && abs(j - ypos[1-turn]) == 1) return true;
}
}
}

// try all
for (int i = 0; i < 4; i++){
for (int j = 0; j < 4; j++){
pii p = grid[i][j];
if (p.X != turn) continue;
if (p.Y == 0) {
for (int k = 0; k < 8; k++){
int i2 = i + dx[k], j2 = j + dy[k];
while (i2 >= 0 && i2 < 4 && j2 >= 0 && j2 < 4) {
if (grid[i2][j2].X == turn) break;
bool capture = (grid[i2][j2].X == 1-turn);
vvpii ngrid = grid;
ngrid[i2][j2] = ngrid[i][j];
ngrid[i][j] = {-1, -1};
vi nxpos = xpos;
vi nypos = ypos;
nxpos[turn] = i2;
nypos[turn] = j2;
if (!f(ngrid, nxpos, nypos, 1-turn, moves - 1)) return true;
if (capture) break;
i2 += dx[k]; j2 += dy[k];
}
}
} else if (p.Y == 1) {
for (int k = 0; k < 8; k++){
int i2 = i + ndx[k], j2 = j + ndy[k];
if (i2 < 0 || i2 >= 4 || j2 < 0 || j2 >= 4) continue;
if (grid[i2][j2].X != turn) {
vvpii ngrid = grid;
ngrid[i2][j2] = ngrid[i][j];
ngrid[i][j] = {-1, -1};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
}
}
} else if (p.Y == 2) {
for (int k = 4; k < 8; k++){
int i2 = i + dx[k], j2 = j + dy[k];
while (i2 >= 0 && i2 < 4 && j2 >= 0 && j2 < 4) {
if (grid[i2][j2].X == turn) break;
bool capture = (grid[i2][j2].X == 1-turn);
vvpii ngrid = grid;
ngrid[i2][j2] = ngrid[i][j];
ngrid[i][j] = {-1, -1};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
if (capture) break;
i2 += dx[k]; j2 += dy[k];
}
}
} else if (p.Y == 3) {
for (int k = 0; k < 4; k++){
int i2 = i + dx[k], j2 = j + dy[k];
while (i2 >= 0 && i2 < 4 && j2 >= 0 && j2 < 4) {
if (grid[i2][j2].X == turn) break;
bool capture = (grid[i2][j2].X == 1-turn);
vvpii ngrid = grid;
ngrid[i2][j2] = ngrid[i][j];
ngrid[i][j] = {-1, -1};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
if (capture) break;
i2 += dx[k]; j2 += dy[k];
}
}
} else {
int i2 = i + pawn[turn], j2 = j;
if (grid[i2][j2].X == -1) {
if (i2 == 0 || i2 == 3) {
vvpii ngrid = grid;
ngrid[i][j] = {-1, -1};
for (int pc = 1; pc <= 3; pc++){
ngrid[i2][j2] = {turn, pc};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
}
} else {
vvpii ngrid = grid;
ngrid[i2][j2] = ngrid[i][j];
ngrid[i][j] = {-1, -1};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
}
}
j2 = j-1;
if (j2 >= 0 && grid[i2][j2].X == 1-turn) {
if (i2 == 0 || i2 == 3) {
vvpii ngrid = grid;
ngrid[i][j] = {-1, -1};
for (int pc = 1; pc <= 3; pc++){
ngrid[i2][j2] = {turn, pc};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
}
} else {
vvpii ngrid = grid;
ngrid[i2][j2] = ngrid[i][j];
ngrid[i][j] = {-1, -1};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
}
}
j2 = j+1;
if (j2 < 4 && grid[i2][j2].X == 1-turn) {
if (i2 == 0 || i2 == 3) {
vvpii ngrid = grid;
ngrid[i][j] = {-1, -1};
for (int pc = 1; pc <= 3; pc++){
ngrid[i2][j2] = {turn, pc};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
}
} else {
vvpii ngrid = grid;
ngrid[i2][j2] = ngrid[i][j];
ngrid[i][j] = {-1, -1};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
}
}
}
}
}
return false;
}

void solve(){
vvpii grid(4, vpii(4, pii(-1, -1)));
int w, b, m; cin >> w >> b >> m;
if (m % 2 == 0) m--;
int wi, wj, bi, bj;
for (int i = 0; i < w; i++){
char piece, cc;
int pc, col, row;
cin >> piece >> cc >> row;
row--;
col = (int)cc - 'A';
pc = pieces.find(piece);
if (pc == 0) {
wi = row;
wj = col;
}
grid[row][col] = pii(0, pc);
}
for (int i = 0; i < b; i++){
char piece, cc;
int pc, col, row;
cin >> piece >> cc >> row;
row--;
col = (int)cc - 'A';
pc = pieces.find(piece);
if (pc == 0) {
bi = row;
bj = col;
}
grid[row][col] = pii(1, pc);
}
if (f(grid, {wi, bi}, {wj, bj}, 0, m)) cout << "YES" << endl;
else cout << "NO" << endl;
}

int main(){
ios::sync_with_stdio(0); cin.tie(0);
int tc; cin >> tc;
while (tc--) solve();

}```
```

```                        ```Solution in Java :

In  Java  :

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
/*
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int g = in.nextInt();
for(int a0 = 0; a0 < g; a0++){
int w = in.nextInt();
int b = in.nextInt();
int m = in.nextInt();
String[][] white = new String[w][3];
for(int white_i=0; white_i < w; white_i++){
for(int white_j=0; white_j < 3; white_j++){
white[white_i][white_j] = in.next();
}
}
String[][] black = new String[b][3];
for(int black_i=0; black_i < b; black_i++){
for(int black_j=0; black_j < 3; black_j++){
black[black_i][black_j] = in.next();
}
}
}
}*/

static class Feature {
public int Qi;
public int Qj;
public int qi;
public int qj;
public List<int[]> wpieces = new ArrayList<>();
public List<int[]> bpieces = new ArrayList<>();
}

static class Move {
public boolean promote = false;
public char promotePiece;
public int srcRow;
public int srcCol;
public char srcPiece;
public int dstRow;
public int dstCol;
public char dstPiece;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int g = in.nextInt();
for(int t = 0; t < g; t++) {
char[][] chess = new char[4][4];
int w = in.nextInt();
int b = in.nextInt();
int m = in.nextInt();
for(int i = 0; i < w; i++) {
char piece = in.next().charAt(0);
int col = in.next().charAt(0) - 'A';
int row = 4 - (in.next().charAt(0) - '0');
chess[row][col] = piece;
}
for(int i = 0; i < b; i++) {
char piece = in.next().charAt(0);
int col = in.next().charAt(0) - 'A';
int row = 4 - (in.next().charAt(0) - '0');
chess[row][col] = (char)(piece + ('a' - 'A'));
}
if(m > 1 && m % 2 == 0) {
m--;
}
System.out.println(evaluate(chess, m, 1) ? "YES" : "NO");
}
}
private static boolean evaluate(char[][] chess, int m, int step) {
Feature f = getFeature(chess);
if(step % 2 == 1) {
if(captureBlack(chess, f)) {
return true;
}
}
if(step == m) {
return false;
}
if(step % 2 == 1) {
for(Move move: getValidMoves(chess, f.wpieces)) {
moveChess(chess, move);
Feature f1 = getFeature(chess);
if(captureWhite(chess, f1)) {
moveBack(chess, move);
continue;
}
if(evaluate(chess, m, step+1)) {
moveBack(chess, move);
return true;
}
moveBack(chess, move);
}
} else {
for(Move move: getValidMoves(chess, f.bpieces)) {
moveChess(chess, move);
if(!evaluate(chess, m, step+1)) {
moveBack(chess, move);
return false;
}
moveBack(chess, move);
}
return true;
}
return false;
}

private static void moveChess(char[][] chess, Move m) {
chess[m.dstRow][m.dstCol] = m.srcPiece;
chess[m.srcRow][m.srcCol] = 0;
if(m.promote) {
chess[m.dstRow][m.dstCol] = m.promotePiece;
}
}

private static void moveBack(char[][] chess, Move m) {
chess[m.dstRow][m.dstCol] = m.dstPiece;
chess[m.srcRow][m.srcCol] = m.srcPiece;
}

private static List<Move> getPromoteMoves(char[][] chess, int srcRow, int srcCol, int dstRow, int dstCol) {
char[] destW = "NBR".toCharArray();
char[] destB = "nbr".toCharArray();
List<Move> moves = new ArrayList<>();

for(int i = 0; i < destW.length; i++) {
Move m = new Move();
m.srcRow = srcRow;
m.srcCol = srcCol;
m.dstRow = dstRow;
m.dstCol = dstCol;
m.promote = true;
m.srcPiece = chess[srcRow][srcCol];
m.dstPiece = chess[dstRow][dstCol];
m.promotePiece = isWhite(chess[srcRow][srcCol]) ? destW[i] : destB[i];
}
return moves;
}

private static boolean shouldPromote(int[] piece, int dstRow) {
char p = (char)piece[0];
if(p == 'P' && dstRow == 0) {
return true;
}
if(p == 'p' && dstRow == 3) {
return true;
}
return false;
}

private static List<Move> getValidMoves(char[][] chess, List<int[]> pieces) {
List<Move> res = new ArrayList<>();
if(pieces.isEmpty()) {
return res;
}
boolean whiteMove = isWhite((char)(pieces.get(0)[0]));

//check promotion
/*
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
if(whiteMove && i == 0 && chess[i][j] == 'P') {
return res;
}
if(!whiteMove && i == 3 && chess[i][j] == 'p') {
return res;
}
}
}*/

for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
if(isWhite(chess[i][j]) && whiteMove) {
continue;
}
if(isBlack(chess[i][j]) && !whiteMove) {
continue;
}
for(int[] p: pieces) {
if(isTarget(chess, p, i, j)) {
if(shouldPromote(p, i)) {
} else {
Move m = new Move();
m.srcRow = p[1];
m.srcCol = p[2];
m.srcPiece = (char)(p[0]);
m.dstRow = i;
m.dstCol = j;
m.dstPiece = chess[i][j];
}
}
}
}
}
return res;
}

private static Feature getFeature(char[][] chess) {
Feature f = new Feature();
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
char c = chess[i][j];
int[] item = new int[3];
item[0] = c;
item[1] = i;
item[2] = j;
if(isWhite(c)) {
}
if(isBlack(c)) {
}
if(c == 'Q') {
f.Qi = i;
f.Qj = j;
}
if(c == 'q') {
f.qi = i;
f.qj = j;
}
}
}
return f;
}
private static boolean isWhite(char c) {
return "QNBRP".indexOf(c) >= 0;
}

private static boolean isBlack(char c) {
return "qnbrp".indexOf(c) >= 0;
}
private static boolean isEmpty(char c) {
return c == 0;
}

private static boolean captureBlack(char[][] chess, Feature f) {
for(int[] p: f.wpieces) {
if(isTarget(chess, p, f.qi, f.qj)) {
return true;
}
}
return false;
}
private static boolean captureWhite(char[][] chess, Feature f) {
for(int[] p: f.bpieces) {
if(isTarget(chess, p, f.Qi, f.Qj)) {
return true;
}
}
return false;
}

private static boolean isTarget(char[][] chess, int[] piece, int row, int col) {
char p = (char)piece[0];
int[] x1 = {0, 0, 1, -1, 1, -1, 1, -1};
int[] y1 = {1, -1, 0, 0, 1, -1, -1, 1};
int[] x2 = {1, -1, 1, -1};
int[] y2 = {1, -1, -1, 1};
int[] x3 = {0, 0, 1, -1};
int[] y3 = {1, -1, 0, 0};
int[] x = x1;
int[] y = y1;

if(p == 'q' || p == 'Q') {
x = x1;
y = y1;
} else if(p == 'n' || p == 'N') {
if(Math.abs(piece[1]-row) == 2 && Math.abs(piece[2]-col) == 1) {
return true;
}
if(Math.abs(piece[1]-row) == 1 && Math.abs(piece[2]-col) == 2) {
return true;
}
return false;
} else if(p == 'P') { //white pawn
if(isEmpty(chess[row][col]) && piece[1] - 1 == row && piece[2] == col) {
return true;
}
if(isBlack(chess[row][col]) && row == piece[1] - 1 && (piece[2]+1 == col || piece[2]-1 == col)) {
return true;
}
return false;
} else if (p == 'p') { //black pawn
if(isEmpty(chess[row][col]) && piece[1] + 1 == row && piece[2] == col) {
return true;
}
if(isWhite(chess[row][col]) && row == piece[1] + 1 && (piece[2]+1 == col || piece[2]-1 == col)) {
return true;
}
return false;
}
else if(p == 'b' || p == 'B') {
x = x2;
y = y2;
} else if(p == 'r' || p == 'R') {
x = x3;
y = y3;
}
for(int d = 0; d < x.length; d++) {
int i = piece[1] + x[d];
int j = piece[2] + y[d];
for(; i >= 0 && i < 4 && j>=0 && j<4; i+=x[d], j+=y[d]) {
if(i != row || j != col) {
if(!isEmpty(chess[i][j])){
break;
}
}
if(i == row && j == col) {
return true;
}
}
}
return false;
}
}```
```

```                        ```Solution in Python :

In  Python3 :

class Piece(object):

def __init__(self, color, ptype, row, col):
self.color = color
self.ptype = ptype
self.row = row
self.col = col
self.captured = False

def valid_moves(self, board):
pass

def move_will_promote(self):
return False

def can_move_to(self, r, c):
if r == self.row and c == self.col:
return False

if r < 0 or r > 3:
return False
if c < 0 or c > 3:
return False

if board.mat[r][c] is None:
return True
elif board.mat[r][c].color != self.color:
return True

return False

def _straight_moves(self, board):
possible = []
# straight up
for row in range(1, 4):
r, c = self.row - row, self.col
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break

# straight down
for row in range(1, 4):
r, c = self.row + row, self.col
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break

# straight left
for col in range(1, 4):
r, c = self.row, self.col - col
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break

# straight right
for col in range(1, 4):
r, c = self.row, self.col + col
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break

return possible

def _diagonal_moves(self, board):
possible = []
# straight left up
for rc in range(1, 4):
r, c = self.row - rc, self.col - rc
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break

# straight left down
for rc in range(1, 4):
r, c = self.row + rc, self.col - rc
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break

# straight right up
for rc in range(1, 4):
r, c = self.row - rc, self.col + rc
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break

# straight right down
for rc in range(1, 4):
r, c = self.row + rc, self.col + rc
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break

return possible

class Rook(Piece):

def valid_moves(self, board):
possible = self._straight_moves(board)
return possible

class Queen(Piece):

def valid_moves(self, board):
possible = self._straight_moves(board) + self._diagonal_moves(board)
return possible

class Knight(Piece):

def valid_moves(self, board):
r, c = self.row, self.col
possible = [
(r - 2, c - 1), (r - 2, c + 1),
(r - 1, c + 2), (r - 1, c - 2),
(r + 1, c + 2), (r + 1, c - 2),
(r + 2, c - 1), (r + 2, c + 1),
]
return [(r, c) for r, c in possible if self.can_move_to(r, c)]

class Bishop(Piece):

def valid_moves(self, board):
possible = self._diagonal_moves(board)
return possible

class Pawn(Piece):

def can_move_to(self, r, c):
if self.ptype == 'P':
if r == self.row and c == self.col:
return False

if r < 0 or r > 3:
return False
if c < 0 or c > 3:
return False

if self.color == "W" and r < self.row:
return False
elif self.color == "B" and self.row < r:
return False

if c == self.col:
if board.mat[r][c] is None:
return True
else:
if board.mat[r][c] is not None and board.mat[r][c].color != self.color:
return True

return False
else:
return Piece.can_move_to(self, r, c)

def move_will_promote(self):
if self.ptype == 'P':
if self.color == "W" and self.row == 2:
return True
elif self.color == "B" and self.row == 1:
return True
return False

def valid_moves(self, board):
if self.ptype == 'P':
r, c = self.row, self.col
possible = [
(r-1, c), (r-1,c-1), (r-1,c+1),
(r+1, c), (r+1,c-1), (r+1,c+1)
]
return [(r, c) for r, c in possible if self.can_move_to(r, c)]
elif self.ptype == 'N':
return Knight.valid_moves(self, board)
elif self.ptype == 'R':
return Rook.valid_moves(self, board)
elif self.ptype == 'B':
return Bishop.valid_moves(self, board)

def promote_to(self, pType):
self.ptype = pType

def undo_promote(self):
self.ptype = 'P'

class Board(object):

def __init__(self):
self.mat = [[None for i in range(4)] for u in range(4)]
self.white = []
self.black = []

def add_piece(self, color, ptype, row, col):
if ptype == "Q":
piece = Queen(color, ptype, row, col)
elif ptype == "N":
piece = Knight(color, ptype, row, col)
elif ptype == "B":
piece = Bishop(color, ptype, row, col)
elif ptype == "R":
piece = Rook(color, ptype, row, col)
elif ptype == "P":
piece = Pawn(color, ptype, row, col)
else:
raise Exception("Invalid type")

self.mat[row][col] = piece
if color == "W":
self.white.append(piece)
elif color == "B":
self.black.append(piece)

def move_to(self, piece, row, col):
self.mat[piece.row][piece.col] = None
if self.mat[row][col] is not None:
captured = self.mat[row][col]
captured.captured = True
self.mat[row][col] = piece
piece.row = row
piece.col = col

def undo_move(self, captured, piece, prev_r, prev_c):
self.move_to(piece, prev_r, prev_c)
if captured:
cr, cc = captured.row, captured.col
self.mat[cr][cc] = captured
captured.captured = False

def is_open(self, r, c):
if r < 0 or r > 3:
return False
if c < 0 or c > 3:
return False
if self.mat[r][c] is None:
return True
return False

def white_can_win(self, turns_left):
if turns_left <= 0:
return False

white_pieces = self.white

q = []
for piece in white_pieces:
if piece.captured is True:
continue

valid_moves = piece.valid_moves(self)
for r, c in valid_moves:
captured = self.mat[r][c]
if captured is not None and captured.ptype == "Q":
return True

q.insert(0, (piece, r, c))

for piece, r, c in q:
prev_r, prev_c = piece.row, piece.col
captured = self.mat[r][c]
willPromote = piece.move_will_promote()
self.move_to(piece, r, c)

if willPromote:
for pType in ['N', 'B', 'R']:
piece.promote_to(pType)
if self.black_cannot_avoid_loss(turns_left - 1):
piece.undo_promote()
self.undo_move(captured, piece, prev_r, prev_c)
return True
piece.undo_promote()
else:
if self.black_cannot_avoid_loss(turns_left - 1):
self.undo_move(captured, piece, prev_r, prev_c)
return True

self.undo_move(captured, piece, prev_r, prev_c)

return False

def black_cannot_avoid_loss(self, turns_left):
if turns_left <= 0:
return False

black_pieces = self.black

for piece in black_pieces:
if piece.captured is True:
continue

valid_moves = piece.valid_moves(self)
for r, c in valid_moves:
prev_r, prev_c = piece.row, piece.col
captured = self.mat[r][c]

if captured is not None and captured.ptype == "Q":
return False
willPromote = piece.move_will_promote()
self.move_to(piece, r, c)
if willPromote:
for pType in ['N', 'B', 'R']:
piece.promote_to(pType)
if not self.white_can_win(turns_left - 1):
piece.undo_promote()
self.undo_move(captured, piece, prev_r, prev_c)
return False
piece.undo_promote()
else:
if not self.white_can_win(turns_left - 1):
self.undo_move(captured, piece, prev_r, prev_c)
return False

self.undo_move(captured, piece, prev_r, prev_c)

return True

if __name__ == '__main__':
games = int(input())
for g in range(games):
board = Board()
cols = "ABCD"
w, b, m = map(int, input().split(" "))
for i in range(w):
ptype, col, row = input().split(" ")
col = cols.index(col)
row = int(row) - 1

for i in range(b):
ptype, col, row = input().split(" ")
col = cols.index(col)
row = int(row) - 1

print("YES" if board.white_can_win(m) else "NO")```
```

## Reverse a doubly linked list

This challenge is part of a tutorial track by MyCodeSchool Given the pointer to the head node of a doubly linked list, reverse the order of the nodes in place. That is, change the next and prev pointers of the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list. Note: The head node might be NULL to indicate that the list is empty.

## Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

## Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

## Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your \$inOrder* func

## Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

## Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.