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];
                        res.add(m);
                    }
                }
            }
        }
        return res;
    } 
    
    private static Feature getFeature(char[][] chess) {
        Feature f = new Feature();
        for(int i = 0; i < 4; i++) {
            for(int j = 0; j < 4; j++) {
                char c = chess[i][j];
                int[] item = new int[3];
                item[0] = c;
                item[1] = i;
                item[2] = j;
                if(isWhite(c)) {
                    f.wpieces.add(item);
                }
                if(isBlack(c)) {
                    f.bpieces.add(item);
                }
                if(c == 'Q') {
                    f.Qi = i;
                    f.Qj = j;
                }
                if(c == 'q') {
                    f.qi = i;
                    f.qj = j;
                }
            }
        }
        return f;
    }
    private static boolean isWhite(char c) {
        return "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;
}