HackerRank Simplified Chess Engine II problem solution YASH PAL, 31 July 2024 In this HackerRank Simplified Chess Engine II problem solution we have given M and the layout of pieces for G games, implement a very basic engine for our simplified version of chess that determines whether or not White can win in <= M moves (regardless of how Black plays) if White always moves first. For each game, print YES on a new line if White can win in <= M moves; otherwise, print NO. Topics we are covering Toggle Problem solution in Python.Problem solution in Java.Problem solution in C++.Problem solution in C. Problem solution in Python. #!/bin/python3 import math import os import random import re import sys def validmoves(piece,posx,posy,whites,blacks,b): if piece=="R": L=[] i=1 while posx+i<4 and not (posx+i,posy) in whites: L+=[("R",posx+i,posy)] if (posx+i,posy) in blacks: break i+=1 i=1 while posx-i>=0 and not (posx-i,posy) in whites: L+=[("R",posx-i,posy)] if (posx-i,posy) in blacks: break i+=1 i=1 while posy+i<4 and not (posx,posy+i) in whites: L+=[("R",posx,posy+i)] if (posx,posy+i) in blacks: break i+=1 i=1 while posy-i>=0 and not (posx,posy-i) in whites: L+=[("R",posx,posy-i)] if (posx,posy-i) in blacks: break i+=1 return(L) elif piece=="B": L=[] i=1 while posx+i<4 and posy+i<4 and not (posx+i,posy+i) in whites: L+=[("B",posx+i,posy+i)] if (posx+i,posy+i) in blacks: break i+=1 i=1 while posx-i>=0 and posy+i<4 and not (posx-i,posy+i) in whites: L+=[("B",posx-i,posy+i)] if (posx-i,posy+i) in blacks: break i+=1 i=1 while posx+i<4 and posy-i>=0 and not (posx+i,posy-i) in whites: L+=[("B",posx+i,posy-i)] if (posx+i,posy-i) in blacks: break i+=1 i=1 while posx-i>=0 and posy-i>=0 and not (posx-i,posy-i) in whites: L+=[("B",posx-i,posy-i)] if (posx-i,posy-i) in blacks: break i+=1 return(L) elif piece=="Q": return([("Q",z[1],z[2]) for z in validmoves("R",posx,posy,whites,blacks,b)+validmoves("B",posx,posy,whites,blacks,b)]) elif piece=="N": return([("N",z[0],z[1]) for z in [(posx+2,posy+1),(posx+2,posy-1),(posx+1,posy+2),(posx+1,posy-2),(posx-1,posy+2),(posx-1,posy-2),(posx-2,posy+1),(posx-2,posy-1)] if not z in whites and 0<=z[0]<=3 and 0<=z[1]<=3]) elif piece=="P": posy+=1-2*b l=[] for i in [-1,1]: if 0<=posx+i<=3 and (posx+i,posy) in blacks: l+=[(posx+i,posy)] if not (posx,posy) in whites+blacks: l+=[(posx,posy)] if posy in [0,3]: return([("N",x[0],x[1]) for x in l]+[("B",x[0],x[1]) for x in l]+[("R",x[0],x[1]) for x in l]) else: return([("P",x[0],x[1]) for x in l]) def simplifiedChessEngine(whites, blacks, moves,b): if moves==0: if b: return("YES") else: return("NO") else: wh=[(x[1],x[2]) for x in whites] bl=[(x[1],x[2]) for x in blacks] i,j=[z[1:] for z in blacks if z[0]=="Q"][0] l=sum([validmoves(x[0],x[1],x[2],wh,bl,b) for x in whites],[]) if (i,j) in [x[1:] for x in l]: return("YES") else: nextmove=[];nextmove2=[] for i in range(len(whites)): for t in validmoves(whites[i][0],whites[i][1],whites[i][2],wh,bl,b): if (t[1],t[2]) in bl: nextmove.append((i,t)) else: nextmove2.append((i,t)) for x in nextmove+nextmove2: i,t=x[0],x[1] piece,posx,posy=whites[i] taken=[z for z in blacks if (z[1],z[2])==t[1:]] blacks=[z for z in blacks if not z in taken] whites[i]=t if simplifiedChessEngine(blacks,whites,moves-1,1-b)=="NO": whites[i]=(piece,posx,posy) blacks+=taken return("YES") else: whites[i]=(piece,posx,posy) blacks+=taken return("NO") if __name__ == '__main__': g = int(input()) for g_itr in range(g): wbm = input().split() w = int(wbm[0]) b = int(wbm[1]) m = int(wbm[2]) whites = [] for _ in range(w): whites.append(input().rstrip().split()) blacks = [] for _ in range(b): blacks.append(input().rstrip().split()) whites=[[x[0],ord(x[1])-65,int(x[2])-1] for x in whites] blacks=[[x[0],ord(x[1])-65,int(x[2])-1] for x in blacks] result = simplifiedChessEngine(whites, blacks, m,0) print(result) # Write Your Code Here Problem solution in Java. import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class SimplifiedChessEngineII { static class Piece { public char type; public boolean isWhite; public Piece (char type, boolean isWhite) { this.type = type; this.isWhite = isWhite; } public Piece (Piece p) { this.type = p.type; this.isWhite = p.isWhite; } } static class Board { public Piece[][] pieces = new Piece[4][4]; public Board(ArrayList<String> w, ArrayList<String> b) { for (String p : w) { String[] p3 = p.split(" "); char type = p3[0].charAt(0); int x = p3[1].charAt(0)-'A'; int y = p3[2].charAt(0)-'1'; pieces[x][y] = new Piece(type, true); } for (String p : b) { String[] p3 = p.split(" "); char type = p3[0].charAt(0); int x = p3[1].charAt(0)-'A'; int y = p3[2].charAt(0)-'1'; pieces[x][y] = new Piece(type, false); } } public Board(Board b) { for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { if (b.pieces[i][j] != null) this.pieces[i][j] = new Piece(b.pieces[i][j]); } } } public ArrayList<Board> legalMoves(boolean whiteToMove) { ArrayList<Board> moves = new ArrayList<Board>(); for (int a = 0; a < 4; a++) { for (int b = 0; b < 4; b++) { if (pieces[a][b] != null && pieces[a][b].isWhite == whiteToMove) { if (pieces[a][b].type == 'P') { int d = whiteToMove?b+1:b-1; if (pieces[a][d] == null) { if (d==0||d==3) { Board newBoard = new Board(this); newBoard.pieces[a][d] = newBoard.pieces[a][b]; newBoard.pieces[a][b] = null; newBoard.pieces[a][d].type = 'R'; moves.add(newBoard); newBoard = new Board(this); newBoard.pieces[a][d] = newBoard.pieces[a][b]; newBoard.pieces[a][b] = null; newBoard.pieces[a][d].type = 'B'; moves.add(newBoard); newBoard = new Board(this); newBoard.pieces[a][d] = newBoard.pieces[a][b]; newBoard.pieces[a][b] = null; newBoard.pieces[a][d].type = 'N'; moves.add(newBoard); } else { Board newBoard = new Board(this); newBoard.pieces[a][d] = newBoard.pieces[a][b]; newBoard.pieces[a][b] = null; moves.add(newBoard); } } for (int c = a-1; c <= a+1; c+=2) { if (c>=0&&c<4) { if (pieces[c][d] != null && pieces[c][d].isWhite != whiteToMove) { if (d==0||d==3) { Board newBoard = new Board(this); newBoard.pieces[c][d] = newBoard.pieces[a][b]; newBoard.pieces[a][b] = null; newBoard.pieces[c][d].type = 'R'; moves.add(newBoard); newBoard = new Board(this); newBoard.pieces[c][d] = newBoard.pieces[a][b]; newBoard.pieces[a][b] = null; newBoard.pieces[c][d].type = 'B'; moves.add(newBoard); newBoard = new Board(this); newBoard.pieces[c][d] = newBoard.pieces[a][b]; newBoard.pieces[a][b] = null; newBoard.pieces[c][d].type = 'N'; moves.add(newBoard); } else { Board newBoard = new Board(this); newBoard.pieces[c][d] = newBoard.pieces[a][b]; newBoard.pieces[a][b] = null; moves.add(newBoard); } } } } } if (pieces[a][b].type == 'N') { for (int c = -2; c <= 2; c+=4) { for (int d = -1; d <= 1; d+=2) { int e = a+c; int f = b+d; int g = a+d; int h = b+c; if (e >= 0 && e < 4 && f >= 0 && f < 4) { if (pieces[e][f] == null || pieces[e][f].isWhite != whiteToMove) { Board newBoard = new Board(this); newBoard.pieces[e][f] = newBoard.pieces[a][b]; newBoard.pieces[a][b] = null; moves.add(newBoard); } } if (g >= 0 && g < 4 && h >= 0 && h < 4) { if (pieces[g][h] == null || pieces[g][h].isWhite != whiteToMove) { Board newBoard = new Board(this); newBoard.pieces[g][h] = newBoard.pieces[a][b]; newBoard.pieces[a][b] = null; moves.add(newBoard); } } } } } if (pieces[a][b].type == 'R' || pieces[a][b].type == 'Q') { for (int c = -1; c <= 1; c += 2) { for (int d = a+c; d >= 0 && d < 4; d += c) { if (pieces[d][b] == null || pieces[d][b].isWhite != whiteToMove) { Board newBoard = new Board(this); newBoard.pieces[d][b] = newBoard.pieces[a][b]; newBoard.pieces[a][b] = null; moves.add(newBoard); } if (pieces[d][b] != null) break; } for (int d = b+c; d >= 0 && d < 4; d += c) { if (pieces[a][d] == null || pieces[a][d].isWhite != whiteToMove) { Board newBoard = new Board(this); newBoard.pieces[a][d] = newBoard.pieces[a][b]; newBoard.pieces[a][b] = null; moves.add(newBoard); } if (pieces[a][d] != null) break; } } } if (pieces[a][b].type == 'B' || pieces[a][b].type == 'Q') { for (int c = -1; c <= 1; c += 2) { for (int d = -1; d <= 1; d += 2) { for (int e = 1; a+e*c >= 0 && a+e*c < 4 && b+e*d >= 0 && b+e*d < 4; e++) { int f = a+e*c; int g = b+e*d; if (pieces[f][g] == null || pieces[f][g].isWhite != whiteToMove) { Board newBoard = new Board(this); newBoard.pieces[f][g] = newBoard.pieces[a][b]; newBoard.pieces[a][b] = null; moves.add(newBoard); } if (pieces[f][g] != null) break; } } } } } } } return moves; } public boolean doesQueenExist(boolean whiteQueen) { for (int a = 0; a < 4; a++) { for (int b = 0; b < 4; b++) { if (pieces[a][b] != null && pieces[a][b].type == 'Q' && pieces[a][b].isWhite == whiteQueen) return true; } } return false; } public boolean canCaptureQueen(boolean whiteToMove) { ArrayList<Board> moves = legalMoves(whiteToMove); for (Board b : moves) { if (!b.doesQueenExist(!whiteToMove)) return true; } return false; } public boolean canReachGoalWhite(int rem) { if (canCaptureQueen(true)) return true; if (rem==1) return false; ArrayList<Board> moves = legalMoves(true); for (Board b : moves) { if (!b.canStopGoalBlack(rem)) return true; } return false; } public boolean canStopGoalBlack(int rem) { if (canCaptureQueen(false)) return true; ArrayList<Board> moves = legalMoves(false); for (Board b : moves) { if (!b.canReachGoalWhite(rem-1)) return true; } return false; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int g = sc.nextInt(); for (int z = 0; z < g; z++) { int w = sc.nextInt(); int b = sc.nextInt(); int m = (sc.nextInt()+1)/2; ArrayList<String> wl = new ArrayList<String>(); ArrayList<String> bl = new ArrayList<String>(); sc.nextLine(); for (int i = 0; i < w; i++) { wl.add(sc.nextLine()); } for (int i = 0; i < b; i++) { bl.add(sc.nextLine()); } Board start = new Board(wl, bl); System.out.println(start.canReachGoalWhite(m)?"YES":"NO"); } } } Problem solution in C++. #include <iostream> #include <cstdio> #include <string> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <stack> #include <cmath> #include <algorithm> #include <cstring> #include <ctime> #include <cassert> #include <cctype> using namespace std; #define pb push_back #define mp make_pair #define pii pair<int,int> #define vi vector<int> #define SZ(x) ((int)(x.size())) #define fi first #define se second #define FOR(i,n) for(int (i)=0;(i)<(n);++(i)) #define FORI(i,n) for(int (i)=1;(i)<=(n);++(i)) #define IN(x,y) ((y).find((x))!=(y).end()) #define ALL(t) t.begin(),t.end() #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i) #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i) #define REMAX(a,b) (a)=max((a),(b)); #define REMIN(a,b) (a)=min((a),(b)); #define DBG cout << "debug here" << endl; #define DBGV(vari) cout << #vari<< " = "<< (vari) <<endl; typedef long long ll; const int T = 1000; const int W = 7; const int M = 6; const int ROWS = 4; const int COLS = 4; string COL_NAMES = "ABCDEFGH"; string COLOR_NAMES = "WB"; #define EMPTY 0 #define QUEEN 1 #define ROOK 2 #define BISHOP 3 #define KNIGHT 4 #define PAWN 5 #define WHITE 0 #define BLACK 1 int codeFigure(char color, char type) { int code; if(type == 'Q') code = QUEEN; else if(type == 'R') code = ROOK; else if(type == 'B') code = BISHOP; else if(type == 'N') code = KNIGHT; else if(type == 'P') code = PAWN; else assert(false); if(color == 'W') code *= 2; else if(color == 'B') code = 2 * code + 1; else assert(false); return code; } int codeFigureFromInts(int color, int type) { return 2 * type + color; } char figureToChar(int figure) { if(figure == EMPTY) return '*'; int color = figure % 2; int type = figure / 2; if(type == QUEEN) return (color == WHITE) ? 'Q' : 'q'; else if(type == ROOK) return (color == WHITE) ? 'R' : 'r'; else if(type == BISHOP) return (color == WHITE) ? 'B' : 'b'; else if(type == KNIGHT) return (color == WHITE) ? 'N' : 'n'; else if(type == PAWN) return (color == WHITE) ? 'P' : 'p'; assert(false); } int getColor(int figure) { assert(figure != EMPTY); return figure % 2; } int getType(int figure) { return figure / 2; } int oppositeColor(int color) { return 1 - color; } typedef vector<vi> Board; void printBoard(Board board) { cout << " A B C D E F G H" << endl; REPD(i, ROWS - 1, 0) { cout << i << " | "; REP(j, 0, COLS - 1) { cout << figureToChar(board[i][j]) << " "; } cout << endl; } } vector<pii> getStraightMoves(pii pos, Board& board) { vector<pii> res; REP(i, pos.fi + 1, ROWS - 1) { auto p = mp(i, pos.se); res.pb(p); if(board[p.fi][p.se] != EMPTY) break; } REPD(i, pos.fi -1, 0) { auto p = mp(i, pos.se); res.pb(p); if(board[p.fi][p.se] != EMPTY) break; } REP(j, pos.se + 1, COLS - 1) { auto p = mp(pos.fi, j); res.pb(p); if(board[p.fi][p.se] != EMPTY) break; } REPD(j, pos.se - 1, 0) { auto p = mp(pos.fi, j); res.pb(p); if(board[p.fi][p.se] != EMPTY) break; } return res; } vector<pii> getDiagonalMoves(pii pos, Board& board) { vector<pii> res; int r = pos.fi + 1; int c = pos.se + 1; while(r < ROWS && c < COLS) { auto p = mp(r, c); res.pb(p); if(board[p.fi][p.se] != EMPTY) break; ++r; ++c; } r = pos.fi - 1; c = pos.se - 1; while(r >= 0 && c >= 0) { auto p = mp(r, c); res.pb(p); if(board[p.fi][p.se] != EMPTY) break; --r; --c; } r = pos.fi + 1; c = pos.se - 1; while(r < ROWS && c >= 0) { auto p = mp(r, c); res.pb(p); if(board[p.fi][p.se] != EMPTY) break; ++r; --c; } r = pos.fi - 1; c = pos.se + 1; while(r >= 0 && c < COLS) { auto p = mp(r, c); res.pb(p); if(board[p.fi][p.se] != EMPTY) break; --r; ++c; } return res; } bool onBoard(pii pos) { return pos.fi >= 0 && pos.fi < ROWS && pos.se >= 0 && pos.se < COLS; } vector<pii> getPawnMoves(pii pos, Board& board) { int color = getColor(board[pos.fi][pos.se]); int row = (color == WHITE) ? pos.fi + 1 : pos.fi - 1; vector<pii> res; auto p = mp(row, pos.se); if(onBoard(p) && board[p.fi][p.se] == EMPTY) { res.pb(p); } p = mp(row, pos.se - 1); if(onBoard(p) && board[p.fi][p.se] != EMPTY && getColor(board[p.fi][p.se]) != getColor(board[pos.fi][pos.se])) { res.pb(p); } p = mp(row, pos.se + 1); if(onBoard(p) && board[p.fi][p.se] != EMPTY && getColor(board[p.fi][p.se]) != getColor(board[pos.fi][pos.se])) { res.pb(p); } return res; } vector<pii> getKnightMoves(pii pos) { vector<pii> res; int r, c; int rs[] = {1, 2,2,1,-1,-2,-2,-1}; int cs[] = {-2,-1,1,2, 2, 1,-1,-2}; FOR(i, 8) { r = pos.fi + rs[i]; c = pos.se + cs[i]; auto p = mp(r, c); if(onBoard(p)) res.pb(p); } return res; } vector<pii> getMoves(int figureType, pii pos, Board& board) { vector<pii> res; vector<pii> tmp; switch(figureType) { case QUEEN: res = getStraightMoves(pos, board); tmp = getDiagonalMoves(pos, board); FOR(i, SZ(tmp)) res.pb(tmp[i]); break; case BISHOP: res = getDiagonalMoves(pos, board); break; case ROOK: res = getStraightMoves(pos, board); break; case KNIGHT: res = getKnightMoves(pos); break; case PAWN: res = getPawnMoves(pos, board); break; default: cout << "! " << figureType << endl; assert(false); } return res; } int solve(int colorToMove, Board board, int remainingMoves) { if(remainingMoves == 0) return BLACK; vector<Board> newBoards; vector<pii> positions; FOR(i, ROWS) FOR(j, COLS) if(board[i][j] != EMPTY && getColor(board[i][j]) == colorToMove) positions.pb(mp(i, j)); FOR(k, positions.size()) { auto pos = positions[k]; auto moves = getMoves(getType(board[pos.fi][pos.se]), pos, board); FOR(j, moves.size()) { auto p = moves[j]; if(board[p.fi][p.se] != EMPTY && getColor(board[p.fi][p.se]) == colorToMove) continue; if(board[p.fi][p.se] != EMPTY && getColor(board[p.fi][p.se]) == oppositeColor(colorToMove) && getType(board[p.fi][p.se]) == QUEEN) { return colorToMove; } if(board[p.fi][p.se] == EMPTY || getColor(board[p.fi][p.se]) == oppositeColor(colorToMove)) { if(getType(board[pos.fi][pos.se]) == PAWN && ((colorToMove == WHITE && p.fi == ROWS - 1) || (colorToMove == BLACK && p.fi == 0))) { auto newBoard = board; newBoard[pos.fi][pos.se] = EMPTY; newBoard[p.fi][p.se] = codeFigureFromInts(colorToMove, BISHOP); newBoards.pb(newBoard); newBoard = board; newBoard[pos.fi][pos.se] = EMPTY; newBoard[p.fi][p.se] = codeFigureFromInts(colorToMove, KNIGHT); newBoards.pb(newBoard); newBoard = board; newBoard[pos.fi][pos.se] = EMPTY; newBoard[p.fi][p.se] = codeFigureFromInts(colorToMove, ROOK); newBoards.pb(newBoard); } else { auto newBoard = board; newBoard[pos.fi][pos.se] = EMPTY; newBoard[p.fi][p.se] = board[pos.fi][pos.se]; newBoards.pb(newBoard); } } } } for(int i = 0; i < newBoards.size(); ++i) { int res = solve(oppositeColor(colorToMove), newBoards[i], remainingMoves - 1); if(res == colorToMove) return colorToMove; } return oppositeColor(colorToMove); } int main() { ios_base::sync_with_stdio(0); int tests; cin >> tests; assert(tests >= 1 && tests <= T); while(tests--) { int w, b, m; cin >> w >> b >> m; assert(w >= 1 && w <= W); assert(b >= 1 && b <= W); assert(m >= 1 && m <= M); Board board = vector<vi> (ROWS, vi(COLS, EMPTY)); set<pii> positions; FOR(i, w + b) { char type; char column; int row; cin >> type >> column >> row; char color = (i < w) ? 'W' : 'B'; int figure = codeFigure(color, type); if(type == 'P') { if(color == 'W') assert(row != ROWS); else if(color == 'B') assert(row != 1); } int found = 0; FOR(j, COLS) if(column == COL_NAMES[j]) found = 1; assert(found); assert(row >= 1 && row <= ROWS); auto pos = mp(row - 1, (int)(column - 'A')); board[pos.fi][pos.se] = figure; positions.insert(pos); } assert(positions.size() == w + b); int res = solve(WHITE, board, m); if(res == WHITE) cout << "YES" << endl; else cout << "NO" << endl; } return 0; } Problem solution in C. #include <stdio.h> #include <string.h> #define QUEEN 1 #define KNIGHT 2 #define BISHOP 3 #define ROOK 4 #define PAWN 5 #define BOUND 8 int m; unsigned char __board[8][8]; unsigned char *_board[8]={__board[0]+2, __board[1]+2, __board[2]+2, __board[3]+2, __board[4]+2, __board[5]+2, __board[6]+2, __board[7]+2}; unsigned char **board=_board+2; unsigned char black[4][4]; int pl[2]={1, -1}; int moves[6][10][3]={ {}, { {-1, -1, 3}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1} }, { {-2, -1, 1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1} }, { {-1, -1, 3}, {-1, 1}, {1, -1}, {1, 1} }, { {-1, 0, 3}, {0, -1}, {0, 1}, {1, 0} }, { {-1, 0, 1}, {-1, -1}, {-1, 1}, {0, 0}, {1, 0}, {1, 1}, {1, -1} } }; static int min(int a, int b) { return a<b?a:b; } static int max(int a, int b) { return a>b?a:b; } void init_game(void) { int i, j; for (i=0; i<8; i++) for (j=0; j<8; j++) __board[i][j]=(BOUND+1)*(!(1<i && i<6 && 1<j && j<6)); memset(black, 0, sizeof(black)); } void print_board(void) { int i, j; char fc[6]={'=', 'Q', 'N', 'B', 'R', 'P'}; for (i=0; i<4; i++, printf("n")) for (j=0; j<4; j++) printf("%c ", fc[board[i][j]]+('a'-'A')*black[i][j]); printf("n"); } int solve(int mv) { int i, j, k, d, b=mv&1; int ni, nj, t, tb, r, mm=pl[!b], prom[5]={0, 0, 0, 0, 0}, p; for (i=0; i<4; i++) { for (j=0; j<4; j++) { if (board[i][j] && black[i][j]==b) { for (k=0; moves[board[i][j]][k][0] || moves[board[i][j]][k][1]; k++) { for (d=1; d<=moves[board[i][j]][0][2]; d++) { if (board[i][j]!=PAWN || k) { if (board[i][j]==PAWN) t=board[ni=(i+moves[board[i][j]][k+b*4][0])][nj=(j+moves[board[i][j]][k+b*4][1])]; else t=board[ni=(i+moves[board[i][j]][k][0]*d)][nj=(j+moves[board[i][j]][k][1]*d)]; if (t) { if (t>BOUND) break; else if (t==QUEEN && black[ni][nj]!=b) return pl[b]; break; } } } } } } } if ((mv+1)==m) return 0; for (i=0; i<4; i++) { for (j=0; j<4; j++) { if (board[i][j] && black[i][j]==b) { for (k=0; moves[board[i][j]][k][0] || moves[board[i][j]][k][1]; k++) { for (d=1, t=0; d<=moves[board[i][j]][0][2] && !t; d++) { prom[0]=board[i][j]; prom[1]=board[i][j]; prom[2]=0; if (board[i][j]==PAWN) { t=board[ni=(i+moves[board[i][j]][k+b*4][0])][nj=(j+moves[board[i][j]][k+b*4][1])]; if (k) { if (t==0 || t>BOUND || black[ni][nj]==b) break; } else if (t) break; if ((ni==0 && !b) || (ni==3 && b)) { prom[1]=KNIGHT; prom[2]=BISHOP; prom[3]=ROOK; prom[4]=0; } } else { t=board[ni=(i+moves[board[i][j]][k][0]*d)][nj=(j+moves[board[i][j]][k][1]*d)]; if (t>BOUND || (t && black[ni][nj]==b)) break; } for (p=1; prom[p]; p++) { tb=black[ni][nj]; board[ni][nj]=prom[p]; black[ni][nj]=b; board[i][j]=0; black[i][j]=0; r=solve(mv+1); board[i][j]=prom[0]; board[ni][nj]=t; black[i][j]=b; black[ni][nj]=tb; if (r==pl[b]) return r; else if (b) mm=min(mm, r); else mm=max(mm, r); } } } } } } return mm; } int main(void) { int i, j, g, r, b, w; char figuremap[26]={['Q'-'A']=QUEEN, ['N'-'A']=KNIGHT, ['B'-'A']=BISHOP, ['R'-'A']=ROOK, ['P'-'A']=PAWN}; char t, c; scanf("%d", &g); for (i=0; i<g; i++) { init_game(); scanf("%d%d%dn", &w, &b, &m); for (j=0; j<w; j++) { scanf("%c %c %dn", &t, &c, &r); board[4-r][c-'A']=figuremap[t-'A']; } for (j=0; j<b; j++) { scanf("%c %c %dn", &t, &c, &r); r=4-r; c-='A'; board[r][c]=figuremap[t-'A']; black[r][c]=1; } printf("%sn", solve(0)==1?"YES":"NO"); } return 0; } Algorithms coding problems solutions