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 :



title-img


                            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();
                }
            }
            // your code goes here
        }
    }*/
    
    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];
            moves.add(m);
        }
        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') {
                    res.addAll(getPromoteMoves(chess, i, j));
                    return res;
                }
                if(!whiteMove && i == 3 && chess[i][j] == 'p') {
                    res.addAll(getPromoteMoves(chess, i, j));
                    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)) {
                            res.addAll(getPromoteMoves(chess, p[1], p[2], i, j));
                        } 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];
                            res.add(m);
                        }
                    }
                }
            }
        }
        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)) {
                    f.wpieces.add(item);
                }
                if(isBlack(c)) {
                    f.bpieces.add(item);
                }
                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
            board.add_piece("W", ptype, row, col)

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

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

View More Similar Problems

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

View Solution →

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

View Solution →

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 -

View Solution →

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

View Solution →

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

View Solution →

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

View Solution →