In this HackerRank Simplified Chess Engine II problem solution we have given M and the layout of pieces for G games, implement a very basic engine for our simplified version of chess that determines whether or not White can win in <= M moves (regardless of how Black plays) if White always moves first. For each game, print YES on a new line if White can win in <= M moves; otherwise, print NO.

HackerRank Simplified Chess Engine II problem solution


Problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

def validmoves(piece,posx,posy,whites,blacks,b):
    if piece=="R":
        L=[]
        i=1
        while posx+i<4 and not (posx+i,posy) in whites:
            L+=[("R",posx+i,posy)]
            if (posx+i,posy) in blacks:
                break
            i+=1
        i=1
        while posx-i>=0 and not (posx-i,posy) in whites:
            L+=[("R",posx-i,posy)]
            if (posx-i,posy) in blacks:
                break
            i+=1
        i=1
        while posy+i<4 and not (posx,posy+i) in whites:
            L+=[("R",posx,posy+i)]
            if (posx,posy+i) in blacks:
                break
            i+=1
        i=1
        while posy-i>=0 and not (posx,posy-i) in whites:
            L+=[("R",posx,posy-i)]
            if (posx,posy-i) in blacks:
                break
            i+=1
        return(L)
    elif piece=="B":
        L=[]
        i=1
        while posx+i<4 and posy+i<4 and not (posx+i,posy+i) in whites:
            L+=[("B",posx+i,posy+i)]
            if (posx+i,posy+i) in blacks:
                break
            i+=1
        i=1
        while posx-i>=0 and posy+i<4 and not (posx-i,posy+i) in whites:
            L+=[("B",posx-i,posy+i)]
            if (posx-i,posy+i) in blacks:
                break
            i+=1
        i=1
        while posx+i<4 and posy-i>=0 and not (posx+i,posy-i) in whites:
            L+=[("B",posx+i,posy-i)]
            if (posx+i,posy-i) in blacks:
                break
            i+=1
        i=1
        while posx-i>=0 and posy-i>=0 and not (posx-i,posy-i) in whites:
            L+=[("B",posx-i,posy-i)]
            if (posx-i,posy-i) in blacks:
                break
            i+=1
        return(L)
    elif piece=="Q":
        return([("Q",z[1],z[2]) for z in validmoves("R",posx,posy,whites,blacks,b)+validmoves("B",posx,posy,whites,blacks,b)])
    elif piece=="N":
        return([("N",z[0],z[1]) for z in [(posx+2,posy+1),(posx+2,posy-1),(posx+1,posy+2),(posx+1,posy-2),(posx-1,posy+2),(posx-1,posy-2),(posx-2,posy+1),(posx-2,posy-1)] if not z in whites and 0<=z[0]<=3 and 0<=z[1]<=3])
    elif piece=="P":
        posy+=1-2*b
        l=[]
        for i in [-1,1]:
            if 0<=posx+i<=3 and (posx+i,posy) in blacks:
                l+=[(posx+i,posy)]
        if not (posx,posy) in whites+blacks:
            l+=[(posx,posy)]
        if posy in [0,3]:
            return([("N",x[0],x[1]) for x in l]+[("B",x[0],x[1]) for x in l]+[("R",x[0],x[1]) for x in l])
        else:
            return([("P",x[0],x[1]) for x in l])

def simplifiedChessEngine(whites, blacks, moves,b):
    if moves==0:
        if b:
            return("YES")
        else:
            return("NO")
    else:
        wh=[(x[1],x[2]) for x in whites]
        bl=[(x[1],x[2]) for x in blacks]
        i,j=[z[1:] for z in blacks if z[0]=="Q"][0]
        l=sum([validmoves(x[0],x[1],x[2],wh,bl,b) for x in whites],[])
        if (i,j) in [x[1:] for x in l]:
            return("YES")
        else:
            nextmove=[];nextmove2=[]
            for i in range(len(whites)):
                for t in validmoves(whites[i][0],whites[i][1],whites[i][2],wh,bl,b):
                    if (t[1],t[2]) in bl:
                        nextmove.append((i,t))
                    else:
                        nextmove2.append((i,t))
            for x in nextmove+nextmove2:
                i,t=x[0],x[1]            
                piece,posx,posy=whites[i]
                taken=[z for z in blacks if (z[1],z[2])==t[1:]]
                blacks=[z for z in blacks if not z in taken]
                whites[i]=t
                if simplifiedChessEngine(blacks,whites,moves-1,1-b)=="NO":
                    whites[i]=(piece,posx,posy)
                    blacks+=taken
                    return("YES")
                else:
                    whites[i]=(piece,posx,posy)
                    blacks+=taken
            return("NO")

if __name__ == '__main__':
    g = int(input())

    for g_itr in range(g):
        wbm = input().split()

        w = int(wbm[0])

        b = int(wbm[1])

        m = int(wbm[2])

        whites = []

        for _ in range(w):
            whites.append(input().rstrip().split())

        blacks = []

        for _ in range(b):
            blacks.append(input().rstrip().split())
        
        whites=[[x[0],ord(x[1])-65,int(x[2])-1] for x in whites]
        blacks=[[x[0],ord(x[1])-65,int(x[2])-1] for x in blacks]

        result = simplifiedChessEngine(whites, blacks, m,0)
        print(result)
        # Write Your Code Here


Problem solution in Java.

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

public class SimplifiedChessEngineII {
    static class Piece {
        public char type;
        public boolean isWhite;

        public Piece (char type, boolean isWhite) {
            this.type = type;
            this.isWhite = isWhite;
        }
        
        public Piece (Piece p) {
            this.type = p.type;
            this.isWhite = p.isWhite;
        }
    }
    
    static class Board {
        public Piece[][] pieces = new Piece[4][4];
        
        public Board(ArrayList<String> w, ArrayList<String> b) {
            for (String p : w) {
                String[] p3 = p.split(" ");
                char type = p3[0].charAt(0);
                int x = p3[1].charAt(0)-'A';
                int y = p3[2].charAt(0)-'1';
                pieces[x][y] = new Piece(type, true);
            }
            for (String p : b) {
                String[] p3 = p.split(" ");
                char type = p3[0].charAt(0);
                int x = p3[1].charAt(0)-'A';
                int y = p3[2].charAt(0)-'1';
                pieces[x][y] = new Piece(type, false);
            }
        }
        
        public Board(Board b) {
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    if (b.pieces[i][j] != null)
                        this.pieces[i][j] = new Piece(b.pieces[i][j]);
                }
            }
        }
        
        public ArrayList<Board> legalMoves(boolean whiteToMove) {
            ArrayList<Board> moves = new ArrayList<Board>();
            for (int a = 0; a < 4; a++) {
                for (int b = 0; b < 4; b++) {
                    if (pieces[a][b] != null && pieces[a][b].isWhite == whiteToMove) {
                        if (pieces[a][b].type == 'P') {
                            int d = whiteToMove?b+1:b-1;
                            if (pieces[a][d] == null) {
                                if (d==0||d==3) {
                                    Board newBoard = new Board(this);
                                    newBoard.pieces[a][d] = newBoard.pieces[a][b];
                                    newBoard.pieces[a][b] = null;
                                    newBoard.pieces[a][d].type = 'R';
                                    moves.add(newBoard);
                                    newBoard = new Board(this);
                                    newBoard.pieces[a][d] = newBoard.pieces[a][b];
                                    newBoard.pieces[a][b] = null;
                                    newBoard.pieces[a][d].type = 'B';
                                    moves.add(newBoard);
                                    newBoard = new Board(this);
                                    newBoard.pieces[a][d] = newBoard.pieces[a][b];
                                    newBoard.pieces[a][b] = null;
                                    newBoard.pieces[a][d].type = 'N';
                                    moves.add(newBoard);
                                }
                                else {
                                    Board newBoard = new Board(this);
                                    newBoard.pieces[a][d] = newBoard.pieces[a][b];
                                    newBoard.pieces[a][b] = null;
                                    moves.add(newBoard);
                                }
                            }
                            for (int c = a-1; c <= a+1; c+=2) {
                                if (c>=0&&c<4) {
                                    if (pieces[c][d] != null && pieces[c][d].isWhite != whiteToMove) {
                                        if (d==0||d==3) {
                                            Board newBoard = new Board(this);
                                            newBoard.pieces[c][d] = newBoard.pieces[a][b];
                                            newBoard.pieces[a][b] = null;
                                            newBoard.pieces[c][d].type = 'R';
                                            moves.add(newBoard);
                                            newBoard = new Board(this);
                                            newBoard.pieces[c][d] = newBoard.pieces[a][b];
                                            newBoard.pieces[a][b] = null;
                                            newBoard.pieces[c][d].type = 'B';
                                            moves.add(newBoard);
                                            newBoard = new Board(this);
                                            newBoard.pieces[c][d] = newBoard.pieces[a][b];
                                            newBoard.pieces[a][b] = null;
                                            newBoard.pieces[c][d].type = 'N';
                                            moves.add(newBoard);
                                        }
                                        else {
                                            Board newBoard = new Board(this);
                                            newBoard.pieces[c][d] = newBoard.pieces[a][b];
                                            newBoard.pieces[a][b] = null;
                                            moves.add(newBoard);
                                        }
                                    }
                                }
                            }
                        }
                        if (pieces[a][b].type == 'N') {
                            for (int c = -2; c <= 2; c+=4) {
                                for (int d = -1; d <= 1; d+=2) {
                                    int e = a+c;
                                    int f = b+d;
                                    int g = a+d;
                                    int h = b+c;
                                    if (e >= 0 && e < 4 && f >= 0 && f < 4) {
                                        if (pieces[e][f] == null || pieces[e][f].isWhite != whiteToMove) {
                                            Board newBoard = new Board(this);
                                            newBoard.pieces[e][f] = newBoard.pieces[a][b];
                                            newBoard.pieces[a][b] = null;
                                            moves.add(newBoard);
                                        }
                                    }
                                    if (g >= 0 && g < 4 && h >= 0 && h < 4) {
                                        if (pieces[g][h] == null || pieces[g][h].isWhite != whiteToMove) {
                                            Board newBoard = new Board(this);
                                            newBoard.pieces[g][h] = newBoard.pieces[a][b];
                                            newBoard.pieces[a][b] = null;
                                            moves.add(newBoard);
                                        }
                                    }
                                }
                            }
                        }
                        if (pieces[a][b].type == 'R' || pieces[a][b].type == 'Q') {
                            for (int c = -1; c <= 1; c += 2) {
                                for (int d = a+c; d >= 0 && d < 4; d += c) {
                                    if (pieces[d][b] == null || pieces[d][b].isWhite != whiteToMove) {
                                        Board newBoard = new Board(this);
                                        newBoard.pieces[d][b] = newBoard.pieces[a][b];
                                        newBoard.pieces[a][b] = null;
                                        moves.add(newBoard);
                                    }
                                    if (pieces[d][b] != null)
                                        break;
                                }
                                for (int d = b+c; d >= 0 && d < 4; d += c) {
                                    if (pieces[a][d] == null || pieces[a][d].isWhite != whiteToMove) {
                                        Board newBoard = new Board(this);
                                        newBoard.pieces[a][d] = newBoard.pieces[a][b];
                                        newBoard.pieces[a][b] = null;
                                        moves.add(newBoard);
                                    }
                                    if (pieces[a][d] != null)
                                        break;
                                }
                            }
                        }
                        if (pieces[a][b].type == 'B' || pieces[a][b].type == 'Q') {
                            for (int c = -1; c <= 1; c += 2) {
                                for (int d = -1; d <= 1; d += 2) {
                                    for (int e = 1; a+e*c >= 0 && a+e*c < 4 && b+e*d >= 0 && b+e*d < 4; e++) {
                                        int f = a+e*c;
                                        int g = b+e*d;
                                        
                                        if (pieces[f][g] == null || pieces[f][g].isWhite != whiteToMove) {
                                            Board newBoard = new Board(this);
                                            newBoard.pieces[f][g] = newBoard.pieces[a][b];
                                            newBoard.pieces[a][b] = null;
                                            moves.add(newBoard);
                                        }
                                        if (pieces[f][g] != null)
                                            break;
                                    }
                                }
                            }
                        }
                    }
                }
            }
            return moves;
        }
        
        public boolean doesQueenExist(boolean whiteQueen) {
            for (int a = 0; a < 4; a++) {
                for (int b = 0; b < 4; b++) {
                    if (pieces[a][b] != null && pieces[a][b].type == 'Q' && pieces[a][b].isWhite == whiteQueen)
                        return true;
                }
            }
            return false;
        }
        
        public boolean canCaptureQueen(boolean whiteToMove) {
            ArrayList<Board> moves = legalMoves(whiteToMove);
            for (Board b : moves) {
                if (!b.doesQueenExist(!whiteToMove))
                    return true;
            }
            return false;
        }
        
        public boolean canReachGoalWhite(int rem) {
            if (canCaptureQueen(true))
                return true;
            if (rem==1)
                return false;
            ArrayList<Board> moves = legalMoves(true);
            for (Board b : moves) {
                if (!b.canStopGoalBlack(rem))
                    return true;
            }
            return false;
        }
        
        public boolean canStopGoalBlack(int rem) {
            if (canCaptureQueen(false))
                return true;
            ArrayList<Board> moves = legalMoves(false);
            for (Board b : moves) {
                if (!b.canReachGoalWhite(rem-1))
                    return true;
            }
            return false;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int g = sc.nextInt();
        for (int z = 0; z < g; z++) {
            int w = sc.nextInt();
            int b = sc.nextInt();
            int m = (sc.nextInt()+1)/2;
            ArrayList<String> wl = new ArrayList<String>();
            ArrayList<String> bl = new ArrayList<String>();
            sc.nextLine();
            for (int i = 0; i < w; i++) {
                wl.add(sc.nextLine());
            }
            for (int i = 0; i < b; i++) {
                bl.add(sc.nextLine());
            }
            Board start = new Board(wl, bl);
            System.out.println(start.canReachGoalWhite(m)?"YES":"NO");
        }
    }
}


Problem solution in C++.

#include <iostream>
#include <cstdio>
#include <string>
#include <sstream> 
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cassert>
#include <cctype>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
#define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))
#define IN(x,y) ((y).find((x))!=(y).end())
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define REMAX(a,b) (a)=max((a),(b));
#define REMIN(a,b) (a)=min((a),(b));
#define DBG cout << "debug here" << endl;
#define DBGV(vari) cout << #vari<< " = "<< (vari) <<endl;

typedef long long ll;

const int T = 1000;
const int W = 7;
const int M = 6;

const int ROWS = 4;
const int COLS = 4;

string COL_NAMES = "ABCDEFGH";
string COLOR_NAMES = "WB";

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

#define WHITE 0
#define BLACK 1

int codeFigure(char color, char type)
{
    int code;
    if(type == 'Q') code = QUEEN;
    else if(type == 'R') code = ROOK;
    else if(type == 'B') code = BISHOP;
    else if(type == 'N') code = KNIGHT;
    else if(type == 'P') code = PAWN;
    else assert(false);

    if(color == 'W') code *= 2;
    else if(color == 'B') code = 2 * code + 1;
    else assert(false);

    return code;
}

int codeFigureFromInts(int color, int type)
{
    return 2 * type + color;
}

char figureToChar(int figure)
{
    if(figure == EMPTY) return '*';
    int color = figure % 2;
    int type = figure / 2;
    if(type == QUEEN) return (color == WHITE) ? 'Q' : 'q';
    else if(type == ROOK) return (color == WHITE) ? 'R' : 'r';
    else if(type == BISHOP) return (color == WHITE) ? 'B' : 'b';
    else if(type == KNIGHT) return (color == WHITE) ? 'N' : 'n';
    else if(type == PAWN) return (color == WHITE) ? 'P' : 'p';
    assert(false);
}

int getColor(int figure) 
{ 
    assert(figure != EMPTY);
    return figure % 2; 
}
int getType(int figure) { return figure / 2; }

int oppositeColor(int color) { return 1 - color; }

typedef vector<vi> Board;

void printBoard(Board board)
{
    cout << "    A B C D E F G H" << endl;
    REPD(i, ROWS - 1, 0)
    {
        cout << i << " | ";
        REP(j, 0, COLS - 1)
        {
            cout << figureToChar(board[i][j]) << " ";
        }
        cout << endl;
    }
}

vector<pii> getStraightMoves(pii pos, Board& board)
{
    vector<pii> res;
    
    REP(i, pos.fi + 1, ROWS - 1) 
    {
        auto p = mp(i, pos.se);
        res.pb(p);
        if(board[p.fi][p.se] != EMPTY) break;
    }
   
    REPD(i, pos.fi -1, 0)
    {
        auto p = mp(i, pos.se);
        res.pb(p);
        if(board[p.fi][p.se] != EMPTY) break;
    }
   
    REP(j, pos.se + 1, COLS - 1)
    {
        auto p = mp(pos.fi, j);
        res.pb(p);
        if(board[p.fi][p.se] != EMPTY) break;
    }
   
    REPD(j, pos.se - 1, 0)
    {
        auto p = mp(pos.fi, j);
        res.pb(p);
        if(board[p.fi][p.se] != EMPTY) break;
    }
    return res;
}

vector<pii> getDiagonalMoves(pii pos, Board& board)
{
    vector<pii> res;
    
    int r = pos.fi + 1;
    int c = pos.se + 1;
    while(r < ROWS && c < COLS)
    {
        auto p = mp(r, c);
        res.pb(p);
        if(board[p.fi][p.se] != EMPTY) break;
        ++r;
        ++c;
    }
    
    r = pos.fi - 1;
    c = pos.se - 1;
    while(r >= 0 && c >= 0)
    {
        auto p = mp(r, c);
        res.pb(p);
        if(board[p.fi][p.se] != EMPTY) break;
        --r;
        --c;
    }
   
    r = pos.fi + 1;
    c = pos.se - 1;
    while(r < ROWS && c >= 0)
    {
        auto p = mp(r, c);
        res.pb(p);
        if(board[p.fi][p.se] != EMPTY) break;
        ++r;
        --c;
    }
   
    r = pos.fi - 1;
    c = pos.se + 1;
    while(r >= 0 && c < COLS)
    {
        auto p = mp(r, c);
        res.pb(p);
        if(board[p.fi][p.se] != EMPTY) break;
        --r;
        ++c;
    }
    return res;
}

bool onBoard(pii pos)
{
    return pos.fi >= 0 && pos.fi < ROWS && pos.se >= 0 && pos.se < COLS;
}

vector<pii> getPawnMoves(pii pos, Board& board)
{
    int color = getColor(board[pos.fi][pos.se]);
    int row = (color == WHITE) ? pos.fi + 1 : pos.fi - 1;
    vector<pii> res;
   
    auto p = mp(row, pos.se);
    if(onBoard(p) && board[p.fi][p.se] == EMPTY)
    {
        res.pb(p);
    }
    
    p = mp(row, pos.se - 1);
    if(onBoard(p) && board[p.fi][p.se] != EMPTY && getColor(board[p.fi][p.se]) != getColor(board[pos.fi][pos.se]))
    {
        res.pb(p);
    }
    
    p = mp(row, pos.se + 1);
    if(onBoard(p) && board[p.fi][p.se] != EMPTY && getColor(board[p.fi][p.se]) != getColor(board[pos.fi][pos.se]))
    {
        res.pb(p);
    }
    return res;
}
vector<pii> getKnightMoves(pii pos)
{
    vector<pii> res;
    int r, c;

    int rs[] = {1,  2,2,1,-1,-2,-2,-1};
    int cs[] = {-2,-1,1,2, 2, 1,-1,-2};
    FOR(i, 8)
    {
        r = pos.fi + rs[i];
        c = pos.se + cs[i];
        auto p = mp(r, c);
        if(onBoard(p)) res.pb(p);
    }
    return res;
}

vector<pii> getMoves(int figureType, pii pos, Board& board)
{
    vector<pii> res;
    vector<pii> tmp;

    switch(figureType)
    {
    case QUEEN:
        res = getStraightMoves(pos, board);
        tmp = getDiagonalMoves(pos, board);
        FOR(i, SZ(tmp)) res.pb(tmp[i]);
        break;
    case BISHOP:
        res = getDiagonalMoves(pos, board);
        break;
    case ROOK:
        res = getStraightMoves(pos, board);
        break;
    case KNIGHT:
        res = getKnightMoves(pos);
        break;
    case PAWN:
        res = getPawnMoves(pos, board);
        break;
    default:
        cout << "! " << figureType << endl;
        assert(false);
    }
    return res;
}

int solve(int colorToMove, Board board, int remainingMoves)
{
    if(remainingMoves == 0) return BLACK;

    vector<Board> newBoards;

    vector<pii> positions;
    FOR(i, ROWS) FOR(j, COLS) if(board[i][j] != EMPTY && getColor(board[i][j]) == colorToMove) positions.pb(mp(i, j));

    FOR(k, positions.size())
    {
        auto pos = positions[k];
        auto moves = getMoves(getType(board[pos.fi][pos.se]), pos, board);
        FOR(j, moves.size())
        {
            auto p = moves[j];

            if(board[p.fi][p.se] != EMPTY && getColor(board[p.fi][p.se]) == colorToMove) continue;

            if(board[p.fi][p.se] != EMPTY && getColor(board[p.fi][p.se]) == oppositeColor(colorToMove) && getType(board[p.fi][p.se]) == QUEEN) 
            {
                return colorToMove;
            }

            if(board[p.fi][p.se] == EMPTY || getColor(board[p.fi][p.se]) == oppositeColor(colorToMove))
            {
       
                if(getType(board[pos.fi][pos.se]) == PAWN && ((colorToMove == WHITE && p.fi == ROWS - 1) || (colorToMove == BLACK && p.fi == 0)))
                {
                    
                    auto newBoard = board;
                    newBoard[pos.fi][pos.se] = EMPTY;
                    newBoard[p.fi][p.se] = codeFigureFromInts(colorToMove, BISHOP);
                    newBoards.pb(newBoard);
                    
                    
                    newBoard = board;
                    newBoard[pos.fi][pos.se] = EMPTY;
                    newBoard[p.fi][p.se] = codeFigureFromInts(colorToMove, KNIGHT);
                    newBoards.pb(newBoard);
                    
                   
                    newBoard = board;
                    newBoard[pos.fi][pos.se] = EMPTY;
                    newBoard[p.fi][p.se] = codeFigureFromInts(colorToMove, ROOK);
                    newBoards.pb(newBoard);
                }
                else
                {
                   
                    auto newBoard = board;
                    newBoard[pos.fi][pos.se] = EMPTY;
                    newBoard[p.fi][p.se] = board[pos.fi][pos.se];
                    newBoards.pb(newBoard);
                }
            }
        }
    }
    for(int i = 0; i < newBoards.size(); ++i)
    {
        int res = solve(oppositeColor(colorToMove), newBoards[i], remainingMoves - 1);
        if(res == colorToMove) return colorToMove;
    }
    return oppositeColor(colorToMove);
}

int main()    
{
    ios_base::sync_with_stdio(0);
    int tests;
    cin >> tests;
    assert(tests >= 1 && tests <= T);

    while(tests--)
    {
        int w, b, m;
        cin >> w >> b >> m;
        assert(w >= 1 && w <= W);
        assert(b >= 1 && b <= W);
        assert(m >= 1 && m <= M);

        Board board = vector<vi> (ROWS, vi(COLS, EMPTY));
        set<pii> positions;
        FOR(i, w + b)
        {
            char type;
            char column;
            int row;
            cin >> type >> column >> row;
            char color = (i < w) ? 'W' : 'B';
            int figure = codeFigure(color, type);
            if(type == 'P')
            {
                if(color == 'W') assert(row != ROWS);
                else if(color == 'B') assert(row != 1);
            }
            int found = 0;
            FOR(j, COLS) if(column == COL_NAMES[j]) found = 1;
            assert(found);
            assert(row >= 1 && row <= ROWS);

            auto pos = mp(row - 1, (int)(column - 'A'));
            board[pos.fi][pos.se] = figure;
            positions.insert(pos);
        }
        assert(positions.size() == w + b);
        int res = solve(WHITE, board, m);
        if(res == WHITE) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}


Problem solution 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},  {0, 1},
    {1, -1},  {1, 0},  {1, 1} },
  { {-2, -1, 1},       {-2, 1},
    {-1, -2},          {-1, 2},
             
    {1, -2},           {1, 2},
    {2, -1},           {2, 1} },
  { {-1, -1, 3},       {-1, 1},
             
    {1, -1},           {1, 1} },
  {           {-1, 0, 3},
    {0, -1},   {0, 1},
              {1, 0} },
  { {-1, 0, 1}, {-1, -1}, {-1, 1},
    {0, 0}, 
    {1, 0},   {1, 1}, {1, -1} } 
};

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;
}