Simplified Chess Engine


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

Board: It's played on a  board between two players named Black and White.
Pieces and Movement:
White initially has  pieces and Black initially has  pieces.
There are no Kings and no Pawns on the board. Each player has exactly one Queen, at most two Rooks, and at most two minor pieces (i.e., a Bishop and/or Knight).
Each piece's possible moves are the same as in classical chess, and each move made by any player counts as a single move.
There is no draw when positions are repeated as there is in classical chess.
Objective: The goal of the game is to capture the opponent’s Queen without losing your own.
Given  and the layout of pieces for  games of simplified chess, implement a very basic (in comparison to the real ones) engine for our simplified version of chess with the ability to determine whether or not White can win in  moves (regardless of how Black plays) if White always moves first. For each game, print YES on a new line if White can win under the specified conditions; otherwise, print NO.

Input Format

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

The first line contains three space-separated integers denoting the respective values of  (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 chesspiece in the format t c r, where  is a character  denoting the type of piece (where  is Queen,  is Knight,  is Bishop, and  is Rook), and  and  denote the respective column and row on the board where the figure is placed (where  and ). These inputs are given as follows:
Each of the  subsequent lines denotes the type and location of a White piece on the board.
Each of the  subsequent lines denotes the type and location of a Black piece on the board.
Constraints

It is guaranteed that the locations of all pieces given as input are distinct.
Each player initially has exactly one Queen, at most two Rooks and at most two minor pieces.


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.



Solution :



title-img


                            Solution in C :

In  C  :






#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct State State;

typedef struct {
    State **data;
    int count;
    int capacity;
} List;

List *list_create(int capacity) {
    List *list = (List *)malloc(sizeof(List));
    list->capacity = (capacity > 0) ? capacity : 8;
    list->count = 0;    
    list->data = (State **)malloc(list->capacity*sizeof(State *));
    assert(list->data);
    return list;
}

void list_destroy(List *list) {
    if (list && list->data) {
        for (int i = 0; i < list->count; i++) free(list->data[i]);
        free(list->data);
    }
    free(list);
}
        
void list_append(List *list, State *item) {
    if (list->count >= list->capacity) {
        list->capacity = 1.5*list->capacity + 1;
        list->data = (State **)realloc(list->data, list->capacity*sizeof(State *));
        assert(list->data);
    }
    list->data[list->count++] = item;
}

/**********************************************************************/

#define TURN_WHITE 0
#define TURN_BLACK 1

#define PIECE_NONE 0

#define COLOR_MASK   0xf0

#define PIECE_MASK   0x0f
#define QUEEN  0x01
#define ROOK   0x02
#define BISHOP 0x03
#define KNIGHT 0x04

#define COLOR_WHITE  0x10
#define WHITE_QUEEN  0x11
#define WHITE_ROOK   0x12
#define WHITE_BISHOP 0x13
#define WHITE_KNIGHT 0x14

#define COLOR_BLACK  0x20
#define BLACK_QUEEN  0x21
#define BLACK_ROOK   0x22
#define BLACK_BISHOP 0x23
#define BLACK_KNIGHT 0x24

struct State {
    char turn;
    unsigned char board[4][4];
};

State *state_new(void) {
    State *s = (State *)malloc(sizeof(State));
    s->turn = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            s->board[i][j] = PIECE_NONE;
        }
    }
    return s;
}

State *state_copy(State *orig) {
    State *copy = (State *)malloc(sizeof(State));
    copy->turn = orig->turn;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            copy->board[i][j] = orig->board[i][j];
        }
    }
    return copy;
}

State *move_piece(State *orig, int i0, int j0, int i1, int j1) {
    State *copy = state_copy(orig);
    copy->turn++;
    copy->board[i1][j1] = copy->board[i0][j0];
    copy->board[i0][j0] = 0;
    return copy;
}

// Returns 1 if winning state for white (meaning black queen has been captured).
// Returns -1 if winning state for black (meaning white queen has been captured).
// Returns 0 for any other state.
int state_utility(State *s) {
    int whiteQueen = 0, blackQueen = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (s->board[i][j] == WHITE_QUEEN) {
                whiteQueen = 1;
                if (blackQueen) return 0;
            } else if (s->board[i][j] == BLACK_QUEEN) {
                blackQueen = 1;
                if (whiteQueen) return 0;
            }
        }
    }
    if (whiteQueen && !blackQueen) return 1;
    if (!whiteQueen && blackQueen) return -1;
    return 0;
}

void state_print(State *s) {
    if (s->turn % 2 == 0) printf("---white's turn (%d)---\n", s->turn);
    else printf("---black's turn (%d)---\n", s->turn);
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            unsigned char piece = s->board[i][j];
            if (!piece) printf(". ");
            else if (piece == WHITE_QUEEN) printf("Q ");
            else if (piece == WHITE_ROOK) printf("R ");
            else if (piece == WHITE_BISHOP) printf("B ");
            else if (piece == WHITE_KNIGHT) printf("N ");
            else if (piece == BLACK_QUEEN) printf("q ");
            else if (piece == BLACK_ROOK) printf("r ");
            else if (piece == BLACK_BISHOP) printf("b ");
            else if (piece == BLACK_KNIGHT) printf("n ");
            else printf("? ");
        }
        printf("\n");
    }
}

List *get_successors(State *s) {
    int color = (s->turn % 2 == 0) ? COLOR_WHITE : COLOR_BLACK;
    List *list = list_create(37);
    
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            unsigned char piece = s->board[i][j];
            if ((piece & COLOR_MASK) != color) continue;
            if ((piece & PIECE_MASK) == QUEEN) {
                for (int ii = i-1; ii >= 0; ii--) {
                    if ((s->board[ii][j] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][j];
                    State *new = move_piece(s, i, j, ii, j);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i+1; ii < 4; ii++) {
                    if ((s->board[ii][j] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][j];
                    State *new = move_piece(s, i, j, ii, j);
                    list_append(list, new);                    
                    if (prev) break;                    
                }
                for (int jj = j-1; jj >= 0; jj--) {
                    if ((s->board[i][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[i][jj];
                    State *new = move_piece(s, i, j, i, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int jj = j+1; jj < 4; jj++) {
                    if ((s->board[i][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[i][jj];
                    State *new = move_piece(s, i, j, i, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i-1, jj = j-1; ii >= 0 && jj >= 0; ii--, jj--) {
                    if ((s->board[ii][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][jj];
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i+1, jj = j-1; ii < 4 && jj >= 0; ii++, jj--) {
                    if ((s->board[ii][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][jj];
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i+1, jj = j+1; ii < 4 && jj < 4; ii++, jj++) {
                    if ((s->board[ii][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][jj];
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i-1, jj = j+1; ii >= 0 && jj < 4; ii--, jj++) {
                    if ((s->board[ii][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][jj];
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                    if (prev) break;
                }                
            } else if ((piece & PIECE_MASK) == ROOK) {
                for (int ii = i-1; ii >= 0; ii--) {
                    if ((s->board[ii][j] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][j];
                    State *new = move_piece(s, i, j, ii, j);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i+1; ii < 4; ii++) {
                    if ((s->board[ii][j] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][j];
                    State *new = move_piece(s, i, j, ii, j);
                    list_append(list, new);                    
                    if (prev) break;                    
                }
                for (int jj = j-1; jj >= 0; jj--) {
                    if ((s->board[i][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[i][jj];
                    State *new = move_piece(s, i, j, i, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int jj = j+1; jj < 4; jj++) {
                    if ((s->board[i][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[i][jj];
                    State *new = move_piece(s, i, j, i, jj);
                    list_append(list, new);
                    if (prev) break;
                }
            } else if ((piece & PIECE_MASK) == BISHOP) {
                for (int ii = i-1, jj = j-1; ii >= 0 && jj >= 0; ii--, jj--) {
                    if ((s->board[ii][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][jj];
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i+1, jj = j-1; ii < 4 && jj >= 0; ii++, jj--) {
                    if ((s->board[ii][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][jj];
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i+1, jj = j+1; ii < 4 && jj < 4; ii++, jj++) {
                    if ((s->board[ii][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][jj];
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                    if (prev) break;
                }
                for (int ii = i-1, jj = j+1; ii >= 0 && jj < 4; ii--, jj++) {
                    if ((s->board[ii][jj] & COLOR_MASK) == color) break;
                    unsigned char prev = s->board[ii][jj];
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                    if (prev) break;
                }
            } else if ((piece & PIECE_MASK) == KNIGHT) {
                int moves[8][2] = {{-2,-1}, {-2,1}, {2,-1}, {2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}};
                for (int k = 0; k < 8; k++) {
                    int ii = i + moves[k][0], jj = j + moves[k][1];
                    if (ii < 0 || ii >= 4 || jj < 0 || jj >= 4) continue; // stay within board
                    if ((s->board[ii][jj] & COLOR_MASK) == color) continue; // can't capture own pieces
                    State *new = move_piece(s, i, j, ii, jj);
                    list_append(list, new);
                }
            }
        }
    }

    return list;
}

int minimax_value(State *s, int maxPly) {
    int u = state_utility(s);
    if (u != 0 || s->turn >= maxPly) return u;
    if (s->turn % 2 == 0) { // white's turn to move
        int maxValue = -100;
        List *list = get_successors(s);
        for (int i = 0; i < list->count; i++) {
            int v = minimax_value(list->data[i], maxPly);
            if (v > maxValue) {
                maxValue = v;
                if (maxValue == 1) break; // can't do any better.
            }
        }
        list_destroy(list);
        return maxValue;
    } else { // black's turn to move
        int minValue = 100;
        List *list = get_successors(s);
        for (int i = 0; i < list->count; i++) {
            int v = minimax_value(list->data[i], maxPly);
            if (v < minValue) {
                minValue = v;
                if (minValue == -1) break; // can't do any better
            }
        }
        list_destroy(list);
        return minValue;
    }
}

int main(void) {
    int g, w, b, m;
    scanf("%d", &g);
    while (g--) {
        scanf("%d %d %d", &w, &b, &m);
        State *s = state_new();
        for (int i = 0; i < w; i++) {
            char t, c, r;
            scanf(" %c %c %c", &t, &c, &r);
            int i = r-'1', j = c-'A';
            if (t == 'Q') s->board[i][j] = WHITE_QUEEN;
            else if (t == 'R') s->board[i][j] = WHITE_ROOK;
            else if (t == 'B') s->board[i][j] = WHITE_BISHOP;
            else if (t == 'N') s->board[i][j] = WHITE_KNIGHT;
            else assert(0);
        }
        for (int i = 0; i < b; i++) {
            char t, c, r;
            scanf(" %c %c %c", &t, &c, &r);
            int i = r-'1', j = c-'A';
            if (t == 'Q') s->board[i][j] = BLACK_QUEEN;
            else if (t == 'R') s->board[i][j] = BLACK_ROOK;
            else if (t == 'B') s->board[i][j] = BLACK_BISHOP;
            else if (t == 'N') s->board[i][j] = BLACK_KNIGHT;
            else assert(0);
        }
        if (m % 2 == 0) m--;
        if (minimax_value(s, m) == 1) printf("YES\n");
        else printf("NO\n");
        free(s);
    }

    return 0;
}
                        


                        Solution in C++ :

In  C ++  :









#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <bitset>
#include <algorithm>
#include <iomanip>

using namespace std;

#define forn(i,n) for (int i = 0; i < int(n); i++)
#define ford(i,n) for (int i = int(n) - 1; i >= 0; i--)
#define fore(i,l,r) for (int i = int(l); i < int(r); i++)
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define x first
#define y second

template<typename X> inline X abs(const X& a) { return a < 0 ? -a : a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
const ld PI = acosl(ld(-1));

const int N = 4;
int a[N][N];
int w, b, m;

inline int getId (const char& c)
{
	if (c == 'Q')
		return 1;
	if (c == 'N')
		return 2;
	if (c == 'B')
		return 3;
	if (c == 'R')
		return 4;
		
	throw;
}

inline bool read()
{
	if (scanf ("%d%d%d", &w, &b, &m) != 3)
		return false;
		
	memset(a, 0, sizeof a);
		
	forn (i, w)
	{
		char c;
		char x;
		int y;
		assert(scanf (" %c %c%d", &c, &x, &y) == 3);
		
		a[x - 'A'][y - 1] = getId(c);
	}
	
	forn (i, b)
	{
		char c;
		char x;
		int y;
		assert(scanf (" %c %c%d", &c, &x, &y) == 3);

		a[x - 'A'][y - 1] = -getId(c);
	}	
	
	return true;
}

map<li, char> d[20];

const int P = 1009;

const int dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dy[8] = {1, 0, -1, 0, 1, -1, 1, -1};

const int dx2[8] = {1, 2, 1, 2, -1, -2, -1, -2};
const int dy2[8] = {2, 1, -2, -1, 2, 1, -2, -1};

inline bool valid (int x, int y)
{
	return x >= 0 && y >= 0 && x < 4 && y < 4;
}

int calc (int h, int m)
{
	if (m == 0)
		return 0;
		
	li hash = h;
	forn (i, 4)
		forn (j, 4)
			hash = hash * P + a[i][j];
			
	if (d[m].count(hash))
		return d[m][hash];
		
	if (h == 0)
	{
		forn (x, 4)
			forn (y, 4)
			{
				if (a[x][y] <= 0)
					continue;
					
				if (a[x][y] == 1)
				{
					forn (k, 8)
					{
						int nx = x + dx[k], ny = y + dy[k];
						while (valid(nx, ny) && a[nx][ny] <= 0)
						{
							int old = a[nx][ny];
							a[nx][ny] = a[x][y];
							a[x][y] = 0;
							
							if (old == -1 || calc(h ^ 1, m - 1))
							{
								a[x][y] = a[nx][ny];
								a[nx][ny] = old;					

								return d[m][hash] = 1;
							}
								
							a[x][y] = a[nx][ny];
							a[nx][ny] = old;
							
							if (a[nx][ny] != 0)
								break;
							
							nx += dx[k], ny += dy[k];
						}
					}
				}
				
				if (a[x][y] == 2)
				{
					forn (k, 8)
					{
						int nx = x + dx2[k], ny = y + dy2[k];
						
						if (!valid(nx, ny) || a[nx][ny] > 0)
							continue;

    					int old = a[nx][ny];
    					a[nx][ny] = a[x][y];
    					a[x][y] = 0;
    					
    					if (old == -1 || calc(h ^ 1, m - 1))
    					{
	    					a[x][y] = a[nx][ny];
    						a[nx][ny] = old;
    					
    						return d[m][hash] = 1;
    					}
    						
    					a[x][y] = a[nx][ny];
    					a[nx][ny] = old;
					}					
				}
				
				if (a[x][y] == 3)
				{
					fore (k, 4, 8)
					{
						int nx = x + dx[k], ny = y + dy[k];
						while (valid(nx, ny) && a[nx][ny] <= 0)
						{
							int old = a[nx][ny];
							a[nx][ny] = a[x][y];
							a[x][y] = 0;
							
							if (old == -1 || calc(h ^ 1, m - 1))
							{
								a[x][y] = a[nx][ny];
								a[nx][ny] = old;
							
								return d[m][hash] = 1;
							}
							
							a[x][y] = a[nx][ny];
							a[nx][ny] = old;							
								
							if (a[nx][ny] != 0)
								break;
							
							nx += dx[k], ny += dy[k];
						}
					}
				}

				if (a[x][y] == 4)
				{
					forn (k, 4)
					{
						int nx = x + dx[k], ny = y + dy[k];
						while (valid(nx, ny) && a[nx][ny] <= 0)
						{
							int old = a[nx][ny];
							a[nx][ny] = a[x][y];
							a[x][y] = 0;
							
							if (old == -1 || calc(h ^ 1, m - 1))
							{
								a[x][y] = a[nx][ny];
								a[nx][ny] = old;
														
								return d[m][hash] = 1;
							}
							
							a[x][y] = a[nx][ny];
							a[nx][ny] = old;							
															
							if (a[nx][ny] != 0)
								break;
							
							nx += dx[k], ny += dy[k];
						}
					}
				}				
			}
			
		return d[m][hash] = 0;
	}
	else
	{
		forn (x, 4)
			forn (y, 4)
			{
				if (a[x][y] >= 0)
					continue;
					
				if (a[x][y] == -1)
				{
					forn (k, 8)
					{
						int nx = x + dx[k], ny = y + dy[k];
						while (valid(nx, ny) && a[nx][ny] >= 0)
						{
							int old = a[nx][ny];
							a[nx][ny] = a[x][y];
							a[x][y] = 0;
							
							if (old == 1 || !calc(h ^ 1, m - 1))
							{
								a[x][y] = a[nx][ny];
								a[nx][ny] = old;
														
								return d[m][hash] = 0;
							}
								
							a[x][y] = a[nx][ny];
							a[nx][ny] = old;
							
							if (a[nx][ny] != 0)
								break;
							
							nx += dx[k], ny += dy[k];
						}
					}
				}
				
				if (a[x][y] == -2)
				{
					forn (k, 8)
					{
						int nx = x + dx2[k], ny = y + dy2[k];
						
						if (!valid(nx, ny) || a[nx][ny] < 0)
							continue;						

    					int old = a[nx][ny];
    					a[nx][ny] = a[x][y];
    					a[x][y] = 0;
    					
    					if (old == 1 || !calc(h ^ 1, m - 1))
    					{
	    					a[x][y] = a[nx][ny];
    						a[nx][ny] = old;
    					
    						return d[m][hash] = 0;
    					}
    						
    					a[x][y] = a[nx][ny];
    					a[nx][ny] = old;
					}					
				}
				
				if (a[x][y] == -3)
				{
					fore (k, 4, 8)
					{
						int nx = x + dx[k], ny = y + dy[k];
						while (valid(nx, ny) && a[nx][ny] >= 0)
						{
							int old = a[nx][ny];
							a[nx][ny] = a[x][y];
							a[x][y] = 0;
							
							if (old == 1 || !calc(h ^ 1, m - 1))
							{
								a[x][y] = a[nx][ny];
								a[nx][ny] = old;
												
								return d[m][hash] = 0;
							}
								
							a[x][y] = a[nx][ny];
							a[nx][ny] = old;
							
							if (a[nx][ny] != 0)
								break;
							
							nx += dx[k], ny += dy[k];
						}
					}
				}

				if (a[x][y] == -4)
				{
					forn (k, 4)
					{
						int nx = x + dx[k], ny = y + dy[k];
						while (valid(nx, ny) && a[nx][ny] >= 0)
						{
							int old = a[nx][ny];
							a[nx][ny] = a[x][y];
							a[x][y] = 0;
							
							if (old == 1 || !calc(h ^ 1, m - 1))
							{
								a[x][y] = a[nx][ny];
								a[nx][ny] = old;
							
								return d[m][hash] = 0;
							}
								
							a[x][y] = a[nx][ny];
							a[nx][ny] = old;
							
							if (a[nx][ny] != 0)
								break;
							
							nx += dx[k], ny += dy[k];
						}
					}
				}				
			}	
			
		return d[m][hash] = 1;
	}
}

inline void solve()
{
	forn (i, m + 1)
		d[i].clear();
		
	int ans = calc(0, m);
	//cerr << ans << endl;
	if (ans)
		puts("YES");
	else
		puts("NO");
}

int main()
{
#ifdef SU2_PROJ
	assert(freopen("input.txt", "r", stdin));
	assert(freopen("output.txt", "w", stdout));
#endif

	cout << setprecision(25) << fixed;
	cerr << setprecision(10) << fixed;

	srand(int(time(NULL)));
	
	int testCnt;
	assert(scanf ("%d", &testCnt) == 1);
	
	forn (test, testCnt)
	{
		assert(read());
		solve();
	}

#ifdef SU2_PROJ
	cerr << "TIME: " << clock() << endl;
#endif

	return 0;
}
                    


                        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 int[] queen = { 1, 0, -1, 0, 0, 1, 0, -1, 2, 0, -2, 0, 0, 2, 0, -2, 3, 0, -3, 0, 0, 3, 0, -3, 1, 1,
			-1, -1, 1, -1, -1, 1, 2, 2, -2, -2, 2, -2, -2, 2, 3, 3, -3, -3, 3, -3, -3, 3 };
	public static int[] rook = { 1, 0, -1, 0, 0, 1, 0, -1, 2, 0, -2, 0, 0, 2, 0, -2, 3, 0, -3, 0, 0, 3, 0, -3 };
	public static int[] bishop = { 1, 1, -1, -1, 1, -1, -1, 1, 2, 2, -2, -2, 2, -2, -2, 2, 3, 3, -3, -3, 3, -3, -3, 3 };
	public static int[] knight = { 1, 2, -1, -2, 2, 1, -2, -1, 1, -2, -1, 2, 2, -1, -2, 1 };

	public abstract static class Piece
	{
		final boolean white;
		final int[] moves;
		final boolean canJump;
		int x, y;
		boolean taken;

		public Piece(int x, int y, boolean white, int[] moves, boolean canJump)
		{
			this.white = white;
			this.x = x;
			this.y = y;
			this.moves = moves;
			this.canJump = canJump;
		}

		int count()
		{
			return moves.length / 2;
		}

		boolean canMove(int number, Piece[][] board)
		{
			int dx = moves[2 * number];
			int dy = moves[2 * number + 1];
			int x = this.x + dx;
			int y = this.y + dy;
			if (!(0 <= x && x <= 3 && 0 <= y && y <= 3))
			{
				return false;
			}
			Piece taking = board[x][y];
			if (taking != null && taking.white == white)
			{
				return false;
			}
			if (canJump)
			{
				return true;
			}
			int steps = Math.max(Math.abs(dx), Math.abs(dy)) - 1;
			int sx = dx == 0 ? 0 : dx > 0 ? 1 : -1;
			int sy = dy == 0 ? 0 : dy > 0 ? 1 : -1;
			for (int i = 1; i <= steps; i++)
			{
				if (board[this.x + sx * i][this.y + sy * i] != null)
				{
					return false;
				}
			}
			return true;
		}

		void move(int number, boolean reverse)
		{
			number += !reverse ? 0 : number % 2 == 0 ? 1 : -1;
			this.x += moves[2 * number];
			this.y += moves[2 * number + 1];
		}

		@Override
		public String toString()
		{
			return (white ? "white " : "black ") + getClass().getSimpleName();
		}
	}

	public static class Queen extends Piece
	{
		public Queen(int x, int y, boolean white)
		{
			super(x, y, white, queen, false);
		}
	}

	public static class Rook extends Piece
	{
		public Rook(int x, int y, boolean white)
		{
			super(x, y, white, rook, false);
		}
	}

	public static class Bishop extends Piece
	{
		public Bishop(int x, int y, boolean white)
		{
			super(x, y, white, bishop, false);
		}
	}

	public static class Knight extends Piece
	{
		public Knight(int x, int y, boolean white)
		{
			super(x, y, white, knight, true);
		}
	}

	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int games = sc.nextInt();
		while (games-- > 0)
		{
			int w = sc.nextInt();
			int b = sc.nextInt();
			int m = sc.nextInt();
			Piece board[][] = new Piece[4][4];
			List<Piece> white = new ArrayList<>();
			List<Piece> black = new ArrayList<>();
			for (int j = 0; j < 2; j++)
			{
				for (int i = 0; i < (j == 0 ? w : b); i++)
				{
					char p = sc.next()
							.charAt(0);
					int x = sc.next()
							.charAt(0) - 'A';
					int y = sc.nextInt() - 1;
					Piece piece = p == 'Q' ? new Queen(x, y, j == 0)
							: p == 'R' ? new Rook(x, y, j == 0)
									: p == 'B' ? new Bishop(x, y, j == 0) : new Knight(x, y, j == 0);
					board[x][y] = piece;
					(j == 0 ? white : black).add(piece);
				}
			}

			boolean win = move(true, white, black, board, m);
			System.out.println(win ? "YES" : "NO");
		}
	}

	public static boolean move(boolean whiteTurn, List<Piece> white, List<Piece> black, Piece[][] board, int m)
	{
		if (m <= 0)
		{
			return false;
		}
		boolean all = !whiteTurn;
		List<Piece> pieces = whiteTurn ? white : black;
		for (Piece piece : pieces)
		{
			if (piece.taken)
			{
				continue;
			}
			for (int i = 0; i < piece.count(); i++)
			{
				if (piece.canMove(i, board))
				{
					board[piece.x][piece.y] = null;
					piece.move(i, false);
					Piece taken = board[piece.x][piece.y];
					board[piece.x][piece.y] = piece;

					if (taken != null)
					{
						taken.taken = true;
					}

					try
					{
						if (taken instanceof Queen)
						{
							return whiteTurn;
						}

						boolean result = move(!whiteTurn, white, black, board, m - 1);

						if (result && whiteTurn)
						{
							return true;
						}
						all &= result;
					}
					finally
					{
						if (taken != null)
						{
							taken.taken = false;
						}

						board[piece.x][piece.y] = taken;
						piece.move(i, true);
						board[piece.x][piece.y] = piece;
					}
				}
			}
		}
		return all;
	}
}
                    


                        Solution in Python : 
                            
In  Python3 :








N = 4
D = ((1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (-1, 1), (-1, -1), (1, -1), (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1))
FIGURES = "QNBR"
RANGE = ((0, 8), (8, 16), (4, 8), (0, 4))


def solve():
	w, b, m = map(int, input().split())
	m -= (m + 1) % 2
	field = [[0] * N for _ in range(N)]
	for i in range(w + b):
		figure, col, row = input().split()
		col = ord(col) - ord('A')
		row = int(row) - 1
		figure = FIGURES.find(figure) + 1
		if i >= w:
			figure *= -1
		field[row][col] = figure
	return search(tuple(map(tuple, field)), m)

def search(field, m):
	if (field, m) in memo:
		return memo[(field, m)]
	white = (m % 2 == 1)
	for i in range(N):
		for j in range(N):
			f = field[i][j]
			if f == 0 or ((f > 0) != white):
				continue
			for d in range(*RANGE[abs(f) - 1]):
				dx, dy = D[d]
				x, y = i, j
				while True:
					x += dx
					y += dy
					if x < 0 or x >= N or y < 0 or y >= N:
						break
					g = field[x][y]
					if g != 0 and (g > 0) == (f > 0):
						break
					if abs(g) == 1:
						memo[(field, m)] = white
						return white
					if m > 1:
						new = list(map(list, field))
						new[i][j] = 0
						new[x][y] = f
						new = tuple(map(tuple, new))
						s = search(new, m - 1)
						if white == s:
							memo[(field, m)] = s
							return s
					if g:
						break
	memo[(field, m)] = not white
	return not white


memo = {}
for _ in range(int(input())):
	print("YES" if solve() else "NO")
                    


View More Similar Problems

Jesse and Cookies

Jesse loves cookies. He wants the sweetness of all his cookies to be greater than value K. To do this, Jesse repeatedly mixes two cookies with the least sweetness. He creates a special combined cookie with: sweetness Least sweet cookie 2nd least sweet cookie). He repeats this procedure until all the cookies in his collection have a sweetness > = K. You are given Jesse's cookies. Print t

View Solution →

Find the Running Median

The median of a set of integers is the midpoint value of the data set for which an equal number of integers are less than and greater than the value. To find the median, you must first sort your set of integers in non-decreasing order, then: If your set contains an odd number of elements, the median is the middle element of the sorted sample. In the sorted set { 1, 2, 3 } , 2 is the median.

View Solution →

Minimum Average Waiting Time

Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h

View Solution →

Merging Communities

People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w

View Solution →

Components in a graph

There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu

View Solution →

Kundu and Tree

Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that

View Solution →