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

Game of Two Stacks

Alexa has two stacks of non-negative integers, stack A = [a0, a1, . . . , an-1 ] and stack B = [b0, b1, . . . , b m-1] where index 0 denotes the top of the stack. Alexa challenges Nick to play the following game: In each move, Nick can remove one integer from the top of either stack A or stack B. Nick keeps a running sum of the integers he removes from the two stacks. Nick is disqualified f

View Solution →

Largest Rectangle

Skyline Real Estate Developers is planning to demolish a number of old, unoccupied buildings and construct a shopping mall in their place. Your task is to find the largest solid area in which the mall can be constructed. There are a number of buildings in a certain two-dimensional landscape. Each building has a height, given by . If you join adjacent buildings, they will form a solid rectangle

View Solution →

Simple Text Editor

In this challenge, you must implement a simple text editor. Initially, your editor contains an empty string, S. You must perform Q operations of the following 4 types: 1. append(W) - Append W string to the end of S. 2 . delete( k ) - Delete the last k characters of S. 3 .print( k ) - Print the kth character of S. 4 . undo( ) - Undo the last (not previously undone) operation of type 1 or 2,

View Solution →

Poisonous Plants

There are a number of plants in a garden. Each of the plants has been treated with some amount of pesticide. After each day, if any plant has more pesticide than the plant on its left, being weaker than the left one, it dies. You are given the initial values of the pesticide in each of the plants. Determine the number of days after which no plant dies, i.e. the time after which there is no plan

View Solution →

AND xor OR

Given an array of distinct elements. Let and be the smallest and the next smallest element in the interval where . . where , are the bitwise operators , and respectively. Your task is to find the maximum possible value of . Input Format First line contains integer N. Second line contains N integers, representing elements of the array A[] . Output Format Print the value

View Solution →

Waiter

You are a waiter at a party. There is a pile of numbered plates. Create an empty answers array. At each iteration, i, remove each plate from the top of the stack in order. Determine if the number on the plate is evenly divisible ith the prime number. If it is, stack it in pile Bi. Otherwise, stack it in stack Ai. Store the values Bi in from top to bottom in answers. In the next iteration, do the

View Solution →