# HackerRank Simplified Chess Engine problem solution

In this HackerRank Simplified Chess Engine problem solution we have given M and the layout of pieces for G 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 <= 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 under the specified conditions; otherwise, print NO.

## Problem solution in Python.

```#!/bin/python3

import os
import sys

def test(ours, theirs, x, y):
if not (0 <= x <= 3 and 0 <= y <= 3):
return -1, -1
for nt in range(len(theirs)):
mm, xx, yy = theirs[nt]
if mm != ' ' and xx == x and yy == y:
return (2 if mm == 'Q' else 1), nt
for mm, xx, yy in ours:
if mm != ' ' and xx == x and yy == y:
return -1, -1
return 0, -1

dn = [(-1, -2), (-2, -1), (-1, 2), (-2, 1), (1, -2), (2, -1), (1, 2), (2, 1)]
dr = [(-1, 0), (1, 0), (0, -1), (0, 1)]
db = [(-1, -1), (-1, 1), (1, -1), (1, 1)]
dq = dr + db

def gen(ours, theirs, xx, yy, d):
if d == dn:
for dx, dy in d:
x, y = xx + dx, yy + dy
t, nt = test(ours, theirs, x, y)
if t >= 0:
yield x, y, t, nt
else:
for dx, dy in d:
x, y = xx, yy
while True:
x, y = x + dx, y + dy
t, nt = test(ours, theirs, x, y)
if t < 0:
break
yield x, y, t, nt
if t > 0:
break

men = {'N': dn, 'B': db, 'R': dr, 'Q': dq}

def solve(ours, theirs, moves):
result = -2
for no in range(len(ours)):
mm, xx, yy = ours[no]
if mm != ' ':
for x, y, t, nt in gen(ours, theirs, xx, yy, men[mm]):
if t == 2:
return 1
if moves > 1:
if nt >= 0:
old = theirs[nt][0]
theirs[nt][0] = ' '
ours[no][1:] = [x, y]
rr = -solve(theirs, ours, moves - 1)
if nt >= 0:
theirs[nt][0] = old
ours[no][1:] = [xx, yy]
result = max(rr, result)
if result == 1:
return 1
return 0 if result == -2 else result

def simplifiedChessEngine(whites, blacks, moves):
if moves % 2 == 0:
moves -= 1
for a in [whites, blacks]:
for b in a:
b[1] = ord(b[1]) - ord('A')
b[2] = ord(b[2]) - ord('1')
return 'YES' if solve(whites, blacks, moves) == 1 else 'NO'

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

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(list(map(lambda x: x[0], input().rstrip().split())))

blacks = []

for _ in range(b):
blacks.append(list(map(lambda x: x[0], input().rstrip().split())))

result = simplifiedChessEngine(whites, blacks, m)
fptr.write(result + '\n')

fptr.close()```

## Problem solution in Java.

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

public class Solution {
static class Feature {
public int Qi;
public int Qj;
public int qi;
public int qj;
public List<int[]> wpieces = new ArrayList<>();
public List<int[]> bpieces = new ArrayList<>();
}

static class Move {
public int srcRow;
public int srcCol;
public char srcPiece;
public int dstRow;
public int dstCol;
public char dstPiece;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int g = in.nextInt();
for(int t = 0; t < g; t++) {
char[][] chess = new char[4][4];
int w = in.nextInt();
int b = in.nextInt();
int m = in.nextInt();
for(int i = 0; i < w; i++) {
char piece = in.next().charAt(0);
int col = in.next().charAt(0) - 'A';
int row = 4 - (in.next().charAt(0) - '0');
chess[row][col] = piece;
}
for(int i = 0; i < b; i++) {
char piece = in.next().charAt(0);
int col = in.next().charAt(0) - 'A';
int row = 4 - (in.next().charAt(0) - '0');
chess[row][col] = (char)(piece + ('a' - 'A'));
}
if(m > 1 && m % 2 == 0) {
m--;
}
System.out.println(evaluate(chess, m, 1) ? "YES" : "NO");
}
}
private static boolean evaluate(char[][] chess, int m, int step) {
Feature f = getFeature(chess);
if(step % 2 == 1) {
if(captureBlack(chess, f)) {
return true;
}
}
if(step == m) {
return false;
}
if(step % 2 == 1) {
for(Move move: getValidMoves(chess, f.wpieces)) {
moveChess(chess, move);
Feature f1 = getFeature(chess);
if(captureWhite(chess, f1)) {
moveBack(chess, move);
continue;
}
if(evaluate(chess, m, step+1)) {
moveBack(chess, move);
return true;
}
moveBack(chess, move);
}
} else {
for(Move move: getValidMoves(chess, f.bpieces)) {
moveChess(chess, move);
if(!evaluate(chess, m, step+1)) {
moveBack(chess, move);
return false;
}
moveBack(chess, move);
}
return true;
}
return false;
}

private static void moveChess(char[][] chess, Move m) {
chess[m.dstRow][m.dstCol] = m.srcPiece;
chess[m.srcRow][m.srcCol] = 0;
}

private static void moveBack(char[][] chess, Move m) {
chess[m.dstRow][m.dstCol] = m.dstPiece;
chess[m.srcRow][m.srcCol] = m.srcPiece;
}

private static List<Move> getValidMoves(char[][] chess, List<int[]> pieces) {
List<Move> res = new ArrayList<>();
if(pieces.isEmpty()) {
return res;
}
boolean whiteMove = isWhite((char)(pieces.get(0)[0]));

for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
if(isWhite(chess[i][j]) && whiteMove) {
continue;
}
if(isBlack(chess[i][j]) && !whiteMove) {
continue;
}
for(int[] p: pieces) {
if(isTarget(chess, p, i, j)) {
Move m = new Move();
m.srcRow = p[1];
m.srcCol = p[2];
m.srcPiece = (char)(p[0]);
m.dstRow = i;
m.dstCol = j;
m.dstPiece = chess[i][j];
}
}
}
}
return res;
}

private static Feature getFeature(char[][] chess) {
Feature f = new Feature();
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
char c = chess[i][j];
int[] item = new int[3];
item[0] = c;
item[1] = i;
item[2] = j;
if(isWhite(c)) {
}
if(isBlack(c)) {
}
if(c == 'Q') {
f.Qi = i;
f.Qj = j;
}
if(c == 'q') {
f.qi = i;
f.qj = j;
}
}
}
return f;
}
private static boolean isWhite(char c) {
return "QNBR".indexOf(c) >= 0;
}

private static boolean isBlack(char c) {
return "qnbr".indexOf(c) >= 0;
}
private static boolean isEmpty(char c) {
return c == 0;
}

private static boolean captureBlack(char[][] chess, Feature f) {
for(int[] p: f.wpieces) {
if(isTarget(chess, p, f.qi, f.qj)) {
return true;
}
}
return false;
}
private static boolean captureWhite(char[][] chess, Feature f) {
for(int[] p: f.bpieces) {
if(isTarget(chess, p, f.Qi, f.Qj)) {
return true;
}
}
return false;
}

private static boolean isTarget(char[][] chess, int[] piece, int row, int col) {
char p = (char)piece[0];
int[] x1 = {0, 0, 1, -1, 1, -1, 1, -1};
int[] y1 = {1, -1, 0, 0, 1, -1, -1, 1};
int[] x2 = {1, -1, 1, -1};
int[] y2 = {1, -1, -1, 1};
int[] x3 = {0, 0, 1, -1};
int[] y3 = {1, -1, 0, 0};
int[] x = x1;
int[] y = y1;

if(p == 'q' || p == 'Q') {
x = x1;
y = y1;
} else if(p == 'n' || p == 'N') {
if(Math.abs(piece[1]-row) == 2 && Math.abs(piece[2]-col) == 1) {
return true;
}
if(Math.abs(piece[1]-row) == 1 && Math.abs(piece[2]-col) == 2) {
return true;
}
return false;
} else if(p == 'b' || p == 'B') {
x = x2;
y = y2;
} else if(p == 'r' || p == 'R') {
x = x3;
y = y3;
}
for(int d = 0; d < x.length; d++) {
int i = piece[1] + x[d];
int j = piece[2] + y[d];
for(; i >= 0 && i < 4 && j>=0 && j<4; i+=x[d], j+=y[d]) {
if(i != row || j != col) {
if(!isEmpty(chess[i][j])){
break;
}
}
if(i == row && j == col) {
return true;
}
}
}
return false;
}
}```

## Problem solution in C++.

```#include <cmath>
#include <cstdio>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define mp make_pair
#define pb push_back
#define forn(i,n) for(int i=0;i<n;i++)

using namespace std;

typedef vector< pair<int,int> > vp;

int board[4][4];

int get(char p) {if (p == 'Q') return 1; if (p == 'N') return 2; if (p == 'B') return 3; return 4;}
int sign(int a) {if(a==0) return 0; if(a<0) return -1; return 1;}
bool canWhite(int);
bool canBlack(int);

vp MOVES(int x, int y) {
int a[] = { 1, -1, 0, 0, 1, 1, -1, -1 }, b[] = { 0, 0, 1, -1, 1, -1, 1, -1 },
s=0, e =8;
vp V;
if (abs(board[x][y]) == 2) {
if (x + 2 >= 0 && x + 2 < 4 && y + 1 >= 0 && y + 1 < 4) V.pb(mp(x + 2, y + 1));
if (x + 2 >= 0 && x + 2 < 4 && y - 1 >= 0 && y - 1 < 4) V.pb(mp(x + 2, y - 1));
if (x - 2 >= 0 && x - 2 < 4 && y + 1 >= 0 && y + 1 < 4) V.pb(mp(x - 2, y + 1));
if (x - 2 >= 0 && x - 2 < 4 && y - 1 >= 0 && y - 1 < 4) V.pb(mp(x - 2, y - 1));
if (x + 1 >= 0 && x + 1 < 4 && y + 2 >= 0 && y + 2 < 4) V.pb(mp(x + 1, y + 2));
if (x + 1 >= 0 && x + 1 < 4 && y - 2 >= 0 && y - 2 < 4) V.pb(mp(x + 1, y - 2));
if (x - 1 >= 0 && x - 1 < 4 && y + 2 >= 0 && y + 2 < 4) V.pb(mp(x - 1, y + 2));
if (x - 1 >= 0 && x - 1 < 4 && y - 2 >= 0 && y - 2 < 4) V.pb(mp(x - 1, y - 2));
return V;
} else if (abs(board[x][y]) == 3) {
s = 4;
} else if (abs(board[x][y]) == 4) {
e=4;
}

int i, j,u,v,_;

for (_ = s; _ < e; _++) {
u = a[_], v = b[_];
i = x + u; j = y + v;
while (i >= 0 && i < 4 && j >= 0 && j < 4 && sign(board[i][j]) != sign(board[x][y])) {
V.pb(mp(i, j));
if (board[i][j] != 0) break;
i += u; j += v;
}
}
return V;
}

bool canWhite(int m) {
if (m <= 0) return false;

for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (board[i][j] <= 0) continue;

vp moves = MOVES(i,j);
for(auto &move : moves){
int a = board[i][j], b = board[move.first][move.second];
if (b == -1) return true;
if (b > 0) continue;
board[move.first][move.second] = a;
board[i][j] = 0;
bool kk = canBlack(m - 1);
board[move.first][move.second] = b;
board[i][j] = a;
if (kk) return true;
}

}
}

return false;
}

bool canBlack(int m) {
if (m <= 1) return false;

for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (board[i][j] >= 0) continue;

vp moves = MOVES(i,j);
for(auto &move : moves){
int a = board[i][j], b = board[move.first][move.second];
if (b == 1) {  return false; }
if (b < 0) continue;
board[move.first][move.second] = a;
board[i][j] = 0;
bool kk = canWhite(m - 1);
board[move.first][move.second] = b;
board[i][j] = a;
if (kk) continue;
return false;
}
}
}
return true;
}
int main() {
int tc,w,b,m,r,c;
char q,k;
cin >> tc;
while(tc--){
memset(board,0,sizeof(board));
cin >> w >> b >> m;
forn(i,w){
cin >> q >> k >> r;
c = k - 'A';
board[r-1][c] = get(q);
}

forn(i,b){
cin >> q >> k >> r;
c = k - 'A';
board[r-1][c] = -get(q);
}

if (canWhite(m))
cout << "YES\n";
else
cout << "NO\n";
}
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}, /*QUEEN*/ {0, 1},
{1, -1},  {1, 0},  {1, 1} },
{ {-2, -1, 1},       {-2, 1},
{-1, -2},          {-1, 2},
/*KNIGHT*/
{1, -2},           {1, 2},
{2, -1},            {2, 1} },
{ {-1, -1, 3},          {-1, 1},
/*BISHOP*/
{1, -1},           {1, 1} },
{           {-1, 0, 3},
{0, -1}, /*ROOK*/ {0, 1},
{1, 0} },
{ {-1, -1, 1}, {-1, 0}
/*PAWN*/ }
};

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];
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-1+2*b)][nj=(j-1+2*b)];
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; d<=moves[board[i][j]][0][2]; d++) {
if (board[i][j]==PAWN) {
if (k) {
t=board[ni=(i-1+2*b)][nj=j];
if (t)
break;
} else {
t=board[ni=(i-1+2*b)][nj=(j-1+2*b)];
if (t==0 || t>BOUND || black[ni][nj]==b)
break;
}
} 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;
}
tb=black[ni][nj];
board[ni][nj]=board[i][j];
black[ni][nj]=b;
board[i][j]=0;
black[i][j]=0;
r=solve(mv+1);
board[i][j]=board[ni][nj];
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);
if (t)
break;
}
}
}
}
}
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;
}```