# 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;
unsigned char *_board={__board+2, __board+2, __board+2, __board+2,
__board+2, __board+2, __board+2, __board+2};
unsigned char **board=_board+2;

unsigned char black;

int pl={1, -1};

int moves={
{},
{ {-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={'=', '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={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] || moves[board[i][j]][k]; k++) {
for (d=1; d<=moves[board[i][j]]; d++) {
if (board[i][j]!=PAWN || k) {
if (board[i][j]==PAWN)
t=board[ni=(i+moves[board[i][j]][k+b*4])][nj=(j+moves[board[i][j]][k+b*4])];
else
t=board[ni=(i+moves[board[i][j]][k]*d)][nj=(j+moves[board[i][j]][k]*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] || moves[board[i][j]][k]; k++) {
for (d=1, t=0; d<=moves[board[i][j]] && !t; d++) {
prom=board[i][j]; prom=board[i][j]; prom=0;
if (board[i][j]==PAWN) {
t=board[ni=(i+moves[board[i][j]][k+b*4])][nj=(j+moves[board[i][j]][k+b*4])];
if (k) {
if (t==0 || t>BOUND || black[ni][nj]==b)
break;
} else if (t)
break;
if ((ni==0 && !b) || (ni==3 && b)) {
prom=KNIGHT; prom=BISHOP; prom=ROOK; prom=0;
}
} else {
t=board[ni=(i+moves[board[i][j]][k]*d)][nj=(j+moves[board[i][j]][k]*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;
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={['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];
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];
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;
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;
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)));

//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;
m.srcCol = p;
m.srcPiece = (char)(p);
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;
item = c;
item = i;
item = 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;
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-row) == 2 && Math.abs(piece-col) == 1) {
return true;
}
if(Math.abs(piece-row) == 1 && Math.abs(piece-col) == 2) {
return true;
}
return false;
} else if(p == 'P') { //white pawn
if(isEmpty(chess[row][col]) && piece - 1 == row && piece == col) {
return true;
}
if(isBlack(chess[row][col]) && row == piece - 1 && (piece+1 == col || piece-1 == col)) {
return true;
}
return false;
} else if (p == 'p') { //black pawn
if(isEmpty(chess[row][col]) && piece + 1 == row && piece == col) {
return true;
}
if(isWhite(chess[row][col]) && row == piece + 1 && (piece+1 == col || piece-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 + x[d];
int j = piece + 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")```
```

## Merge two sorted linked lists

This challenge is part of a tutorial track by MyCodeSchool Given pointers to the heads of two sorted linked lists, merge them into a single, sorted linked list. Either head pointer may be null meaning that the corresponding list is empty. Example headA refers to 1 -> 3 -> 7 -> NULL headB refers to 1 -> 2 -> NULL The new list is 1 -> 1 -> 2 -> 3 -> 7 -> NULL. Function Description C

## Get Node Value

This challenge is part of a tutorial track by MyCodeSchool Given a pointer to the head of a linked list and a specific position, determine the data value at that position. Count backwards from the tail node. The tail is at postion 0, its parent is at 1 and so on. Example head refers to 3 -> 2 -> 1 -> 0 -> NULL positionFromTail = 2 Each of the data values matches its distance from the t

## Delete duplicate-value nodes from a sorted linked list

This challenge is part of a tutorial track by MyCodeSchool You are given the pointer to the head node of a sorted linked list, where the data in the nodes is in ascending order. Delete nodes and return a sorted list with each distinct value in the original list. The given head pointer may be null indicating that the list is empty. Example head refers to the first node in the list 1 -> 2 -

## Cycle Detection

A linked list is said to contain a cycle if any node is visited more than once while traversing the list. Given a pointer to the head of a linked list, determine if it contains a cycle. If it does, return 1. Otherwise, return 0. Example head refers 1 -> 2 -> 3 -> NUL The numbers shown are the node numbers, not their data values. There is no cycle in this list so return 0. head refer

## Find Merge Point of Two Lists

This challenge is part of a tutorial track by MyCodeSchool Given pointers to the head nodes of 2 linked lists that merge together at some point, find the node where the two lists merge. The merge point is where both lists point to the same node, i.e. they reference the same memory location. It is guaranteed that the two head nodes will be different, and neither will be NULL. If the lists share

## Inserting a Node Into a Sorted Doubly Linked List

Given a reference to the head of a doubly-linked list and an integer ,data , create a new DoublyLinkedListNode object having data value data and insert it at the proper location to maintain the sort. Example head refers to the list 1 <-> 2 <-> 4 - > NULL. data = 3 Return a reference to the new list: 1 <-> 2 <-> 4 - > NULL , Function Description Complete the sortedInsert function