Simplified Chess Engine II
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 to find tactical ideas. Consider the following simplified version of chess: Board: It's played on a board between two players named Black and White. Rows are numbered from to , where the top row is and the bottom row is . Columns are lettered from to , where the leftmost column is and the rightmost column is . Pieces and Movement: White initially has pieces and Black initially has pieces. There are no Kings on the board. Each player initially has exactly Queen, at most Pawns, at most Rooks, and at most minor pieces (i.e., a Bishop and/or Knight). White's Pawns move up the board, while Black's Pawns move down the board. Each move made by any player counts as a single move. Each piece's possible moves are the same as in classical chess, with the following exceptions: Pawns cannot move two squares forward. The en passant move is not possible. Promotion: Pawns promote to either a Bishop, Knight, or Rook when they reach the back row (promotion to a Queen is not allowed). The players must perform promotions whenever possible. This means White must promote their Pawns when they reach any cell in the top row, and Black must promote their Pawns when they reach any cell in the bottom row. Objective: The goal of the game is to capture the opponent’s Queen without losing your own. There will never be a draw or tie scenario like you might see in classical chess. Given and the layout of pieces for games, implement a very basic engine for our simplified version of chess that determines 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 in moves; otherwise, print NO. Input Format The first line contains an integer, , denoting the number of games. The subsequent lines describe each game in the following format: The first line contains three space-separated integers describing 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 chess piece in the form t c r, where is a character denoting the type of piece (where is Queen, is Knight, is Bishop, is Rook, and is a Pawn), and and denote the respective column and row on the board where the figure is located (where and ). These inputs are given as follows: Each of the first lines describes the type and location of a White piece. Each of the subsequent lines describes the type and location of a Black piece. 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 instead.
Solution :
Solution in C :
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, 0, 1}, {-1, -1}, {-1, 1}, /* white */
{0, 0}, /*PAWN*/
{1, 0}, {1, 1}, {1, -1} } /* for black */
};
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%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;
}
Solution in C++ :
In C ++ :
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
string pieces = "QNBRP";
int ndx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int ndy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
int pawn[] = {1, -1};
int dx[] = {-1, 0, 0, 1, -1, -1, 1, 1};
int dy[] = {0, -1, 1, 0, -1, 1, -1, 1};
int sq(int x) { return x * x; }
bool f(const vvpii &grid, vi xpos, vi ypos, int turn, int moves){
if (moves == 0) return true;
// can capture queen
for (int i = 0; i < 4; i++){
for (int j = 0; j < 4; j++){
pii p = grid[i][j];
if (p.X != turn) continue;
if (p.Y == 0) {
for (int k = 0; k < 8; k++){
int i2 = i + dx[k], j2 = j + dy[k];
while (i2 >= 0 && i2 < 4 && j2 >= 0 && j2 < 4) {
if (i2 == xpos[1-turn] && j2 == ypos[1-turn]) return true;
if (grid[i2][j2].X != -1) break;
i2 += dx[k]; j2 += dy[k];
}
}
} else if (p.Y == 1) {
if (sq(i - xpos[1-turn]) + sq(j - ypos[1-turn]) == 5) return true;
} else if (p.Y == 2) {
for (int k = 4; k < 8; k++){
int i2 = i + dx[k], j2 = j + dy[k];
while (i2 >= 0 && i2 < 4 && j2 >= 0 && j2 < 4) {
if (i2 == xpos[1-turn] && j2 == ypos[1-turn]) return true;
if (grid[i2][j2].X != -1) break;
i2 += dx[k]; j2 += dy[k];
}
}
} else if (p.Y == 3) {
for (int k = 0; k < 4; k++){
int i2 = i + dx[k], j2 = j + dy[k];
while (i2 >= 0 && i2 < 4 && j2 >= 0 && j2 < 4) {
if (i2 == xpos[1-turn] && j2 == ypos[1-turn]) return true;
if (grid[i2][j2].X != -1) break;
i2 += dx[k]; j2 += dy[k];
}
}
} else {
if (i + pawn[turn] == xpos[1-turn] && abs(j - ypos[1-turn]) == 1) return true;
}
}
}
// try all
for (int i = 0; i < 4; i++){
for (int j = 0; j < 4; j++){
pii p = grid[i][j];
if (p.X != turn) continue;
if (p.Y == 0) {
for (int k = 0; k < 8; k++){
int i2 = i + dx[k], j2 = j + dy[k];
while (i2 >= 0 && i2 < 4 && j2 >= 0 && j2 < 4) {
if (grid[i2][j2].X == turn) break;
bool capture = (grid[i2][j2].X == 1-turn);
vvpii ngrid = grid;
ngrid[i2][j2] = ngrid[i][j];
ngrid[i][j] = {-1, -1};
vi nxpos = xpos;
vi nypos = ypos;
nxpos[turn] = i2;
nypos[turn] = j2;
if (!f(ngrid, nxpos, nypos, 1-turn, moves - 1)) return true;
if (capture) break;
i2 += dx[k]; j2 += dy[k];
}
}
} else if (p.Y == 1) {
for (int k = 0; k < 8; k++){
int i2 = i + ndx[k], j2 = j + ndy[k];
if (i2 < 0 || i2 >= 4 || j2 < 0 || j2 >= 4) continue;
if (grid[i2][j2].X != turn) {
vvpii ngrid = grid;
ngrid[i2][j2] = ngrid[i][j];
ngrid[i][j] = {-1, -1};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
}
}
} else if (p.Y == 2) {
for (int k = 4; k < 8; k++){
int i2 = i + dx[k], j2 = j + dy[k];
while (i2 >= 0 && i2 < 4 && j2 >= 0 && j2 < 4) {
if (grid[i2][j2].X == turn) break;
bool capture = (grid[i2][j2].X == 1-turn);
vvpii ngrid = grid;
ngrid[i2][j2] = ngrid[i][j];
ngrid[i][j] = {-1, -1};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
if (capture) break;
i2 += dx[k]; j2 += dy[k];
}
}
} else if (p.Y == 3) {
for (int k = 0; k < 4; k++){
int i2 = i + dx[k], j2 = j + dy[k];
while (i2 >= 0 && i2 < 4 && j2 >= 0 && j2 < 4) {
if (grid[i2][j2].X == turn) break;
bool capture = (grid[i2][j2].X == 1-turn);
vvpii ngrid = grid;
ngrid[i2][j2] = ngrid[i][j];
ngrid[i][j] = {-1, -1};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
if (capture) break;
i2 += dx[k]; j2 += dy[k];
}
}
} else {
int i2 = i + pawn[turn], j2 = j;
if (grid[i2][j2].X == -1) {
if (i2 == 0 || i2 == 3) {
vvpii ngrid = grid;
ngrid[i][j] = {-1, -1};
for (int pc = 1; pc <= 3; pc++){
ngrid[i2][j2] = {turn, pc};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
}
} else {
vvpii ngrid = grid;
ngrid[i2][j2] = ngrid[i][j];
ngrid[i][j] = {-1, -1};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
}
}
j2 = j-1;
if (j2 >= 0 && grid[i2][j2].X == 1-turn) {
if (i2 == 0 || i2 == 3) {
vvpii ngrid = grid;
ngrid[i][j] = {-1, -1};
for (int pc = 1; pc <= 3; pc++){
ngrid[i2][j2] = {turn, pc};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
}
} else {
vvpii ngrid = grid;
ngrid[i2][j2] = ngrid[i][j];
ngrid[i][j] = {-1, -1};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
}
}
j2 = j+1;
if (j2 < 4 && grid[i2][j2].X == 1-turn) {
if (i2 == 0 || i2 == 3) {
vvpii ngrid = grid;
ngrid[i][j] = {-1, -1};
for (int pc = 1; pc <= 3; pc++){
ngrid[i2][j2] = {turn, pc};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
}
} else {
vvpii ngrid = grid;
ngrid[i2][j2] = ngrid[i][j];
ngrid[i][j] = {-1, -1};
if (!f(ngrid, xpos, ypos, 1-turn, moves - 1)) return true;
}
}
}
}
}
return false;
}
void solve(){
vvpii grid(4, vpii(4, pii(-1, -1)));
int w, b, m; cin >> w >> b >> m;
if (m % 2 == 0) m--;
int wi, wj, bi, bj;
for (int i = 0; i < w; i++){
char piece, cc;
int pc, col, row;
cin >> piece >> cc >> row;
row--;
col = (int)cc - 'A';
pc = pieces.find(piece);
if (pc == 0) {
wi = row;
wj = col;
}
grid[row][col] = pii(0, pc);
}
for (int i = 0; i < b; i++){
char piece, cc;
int pc, col, row;
cin >> piece >> cc >> row;
row--;
col = (int)cc - 'A';
pc = pieces.find(piece);
if (pc == 0) {
bi = row;
bj = col;
}
grid[row][col] = pii(1, pc);
}
if (f(grid, {wi, bi}, {wj, bj}, 0, m)) cout << "YES" << endl;
else cout << "NO" << endl;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int tc; cin >> tc;
while (tc--) solve();
}
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 void main(String[] args) {
Scanner in = new Scanner(System.in);
int g = in.nextInt();
for(int a0 = 0; a0 < g; a0++){
int w = in.nextInt();
int b = in.nextInt();
int m = in.nextInt();
String[][] white = new String[w][3];
for(int white_i=0; white_i < w; white_i++){
for(int white_j=0; white_j < 3; white_j++){
white[white_i][white_j] = in.next();
}
}
String[][] black = new String[b][3];
for(int black_i=0; black_i < b; black_i++){
for(int black_j=0; black_j < 3; black_j++){
black[black_i][black_j] = in.next();
}
}
// your code goes here
}
}*/
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 boolean promote = false;
public char promotePiece;
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;
if(m.promote) {
chess[m.dstRow][m.dstCol] = m.promotePiece;
}
}
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> getPromoteMoves(char[][] chess, int srcRow, int srcCol, int dstRow, int dstCol) {
char[] destW = "NBR".toCharArray();
char[] destB = "nbr".toCharArray();
List<Move> moves = new ArrayList<>();
for(int i = 0; i < destW.length; i++) {
Move m = new Move();
m.srcRow = srcRow;
m.srcCol = srcCol;
m.dstRow = dstRow;
m.dstCol = dstCol;
m.promote = true;
m.srcPiece = chess[srcRow][srcCol];
m.dstPiece = chess[dstRow][dstCol];
m.promotePiece = isWhite(chess[srcRow][srcCol]) ? destW[i] : destB[i];
moves.add(m);
}
return moves;
}
private static boolean shouldPromote(int[] piece, int dstRow) {
char p = (char)piece[0];
if(p == 'P' && dstRow == 0) {
return true;
}
if(p == 'p' && dstRow == 3) {
return true;
}
return false;
}
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]));
//check promotion
/*
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
if(whiteMove && i == 0 && chess[i][j] == 'P') {
res.addAll(getPromoteMoves(chess, i, j));
return res;
}
if(!whiteMove && i == 3 && chess[i][j] == 'p') {
res.addAll(getPromoteMoves(chess, i, j));
return res;
}
}
}*/
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)) {
if(shouldPromote(p, i)) {
res.addAll(getPromoteMoves(chess, p[1], p[2], i, j));
} else {
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 "QNBRP".indexOf(c) >= 0;
}
private static boolean isBlack(char c) {
return "qnbrp".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 == 'P') { //white pawn
if(isEmpty(chess[row][col]) && piece[1] - 1 == row && piece[2] == col) {
return true;
}
if(isBlack(chess[row][col]) && row == piece[1] - 1 && (piece[2]+1 == col || piece[2]-1 == col)) {
return true;
}
return false;
} else if (p == 'p') { //black pawn
if(isEmpty(chess[row][col]) && piece[1] + 1 == row && piece[2] == col) {
return true;
}
if(isWhite(chess[row][col]) && row == piece[1] + 1 && (piece[2]+1 == col || piece[2]-1 == col)) {
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;
}
}
Solution in Python :
In Python3 :
class Piece(object):
def __init__(self, color, ptype, row, col):
self.color = color
self.ptype = ptype
self.row = row
self.col = col
self.captured = False
def valid_moves(self, board):
pass
def move_will_promote(self):
return False
def can_move_to(self, r, c):
if r == self.row and c == self.col:
return False
if r < 0 or r > 3:
return False
if c < 0 or c > 3:
return False
if board.mat[r][c] is None:
return True
elif board.mat[r][c].color != self.color:
return True
return False
def _straight_moves(self, board):
possible = []
# straight up
for row in range(1, 4):
r, c = self.row - row, self.col
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break
# straight down
for row in range(1, 4):
r, c = self.row + row, self.col
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break
# straight left
for col in range(1, 4):
r, c = self.row, self.col - col
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break
# straight right
for col in range(1, 4):
r, c = self.row, self.col + col
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break
return possible
def _diagonal_moves(self, board):
possible = []
# straight left up
for rc in range(1, 4):
r, c = self.row - rc, self.col - rc
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break
# straight left down
for rc in range(1, 4):
r, c = self.row + rc, self.col - rc
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break
# straight right up
for rc in range(1, 4):
r, c = self.row - rc, self.col + rc
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break
# straight right down
for rc in range(1, 4):
r, c = self.row + rc, self.col + rc
if self.can_move_to(r, c):
possible.append((r, c))
if not board.is_open(r, c):
break
return possible
class Rook(Piece):
def valid_moves(self, board):
possible = self._straight_moves(board)
return possible
class Queen(Piece):
def valid_moves(self, board):
possible = self._straight_moves(board) + self._diagonal_moves(board)
return possible
class Knight(Piece):
def valid_moves(self, board):
r, c = self.row, self.col
possible = [
(r - 2, c - 1), (r - 2, c + 1),
(r - 1, c + 2), (r - 1, c - 2),
(r + 1, c + 2), (r + 1, c - 2),
(r + 2, c - 1), (r + 2, c + 1),
]
return [(r, c) for r, c in possible if self.can_move_to(r, c)]
class Bishop(Piece):
def valid_moves(self, board):
possible = self._diagonal_moves(board)
return possible
class Pawn(Piece):
def can_move_to(self, r, c):
if self.ptype == 'P':
if r == self.row and c == self.col:
return False
if r < 0 or r > 3:
return False
if c < 0 or c > 3:
return False
if self.color == "W" and r < self.row:
return False
elif self.color == "B" and self.row < r:
return False
if c == self.col:
if board.mat[r][c] is None:
return True
else:
if board.mat[r][c] is not None and board.mat[r][c].color != self.color:
return True
return False
else:
return Piece.can_move_to(self, r, c)
def move_will_promote(self):
if self.ptype == 'P':
if self.color == "W" and self.row == 2:
return True
elif self.color == "B" and self.row == 1:
return True
return False
def valid_moves(self, board):
if self.ptype == 'P':
r, c = self.row, self.col
possible = [
(r-1, c), (r-1,c-1), (r-1,c+1),
(r+1, c), (r+1,c-1), (r+1,c+1)
]
return [(r, c) for r, c in possible if self.can_move_to(r, c)]
elif self.ptype == 'N':
return Knight.valid_moves(self, board)
elif self.ptype == 'R':
return Rook.valid_moves(self, board)
elif self.ptype == 'B':
return Bishop.valid_moves(self, board)
def promote_to(self, pType):
self.ptype = pType
def undo_promote(self):
self.ptype = 'P'
class Board(object):
def __init__(self):
self.mat = [[None for i in range(4)] for u in range(4)]
self.white = []
self.black = []
def add_piece(self, color, ptype, row, col):
if ptype == "Q":
piece = Queen(color, ptype, row, col)
elif ptype == "N":
piece = Knight(color, ptype, row, col)
elif ptype == "B":
piece = Bishop(color, ptype, row, col)
elif ptype == "R":
piece = Rook(color, ptype, row, col)
elif ptype == "P":
piece = Pawn(color, ptype, row, col)
else:
raise Exception("Invalid type")
self.mat[row][col] = piece
if color == "W":
self.white.append(piece)
elif color == "B":
self.black.append(piece)
def move_to(self, piece, row, col):
self.mat[piece.row][piece.col] = None
if self.mat[row][col] is not None:
captured = self.mat[row][col]
captured.captured = True
self.mat[row][col] = piece
piece.row = row
piece.col = col
def undo_move(self, captured, piece, prev_r, prev_c):
self.move_to(piece, prev_r, prev_c)
if captured:
cr, cc = captured.row, captured.col
self.mat[cr][cc] = captured
captured.captured = False
def is_open(self, r, c):
if r < 0 or r > 3:
return False
if c < 0 or c > 3:
return False
if self.mat[r][c] is None:
return True
return False
def white_can_win(self, turns_left):
if turns_left <= 0:
return False
white_pieces = self.white
q = []
for piece in white_pieces:
if piece.captured is True:
continue
valid_moves = piece.valid_moves(self)
for r, c in valid_moves:
captured = self.mat[r][c]
if captured is not None and captured.ptype == "Q":
return True
q.insert(0, (piece, r, c))
for piece, r, c in q:
prev_r, prev_c = piece.row, piece.col
captured = self.mat[r][c]
willPromote = piece.move_will_promote()
self.move_to(piece, r, c)
if willPromote:
for pType in ['N', 'B', 'R']:
piece.promote_to(pType)
if self.black_cannot_avoid_loss(turns_left - 1):
piece.undo_promote()
self.undo_move(captured, piece, prev_r, prev_c)
return True
piece.undo_promote()
else:
if self.black_cannot_avoid_loss(turns_left - 1):
self.undo_move(captured, piece, prev_r, prev_c)
return True
self.undo_move(captured, piece, prev_r, prev_c)
return False
def black_cannot_avoid_loss(self, turns_left):
if turns_left <= 0:
return False
black_pieces = self.black
for piece in black_pieces:
if piece.captured is True:
continue
valid_moves = piece.valid_moves(self)
for r, c in valid_moves:
prev_r, prev_c = piece.row, piece.col
captured = self.mat[r][c]
if captured is not None and captured.ptype == "Q":
return False
willPromote = piece.move_will_promote()
self.move_to(piece, r, c)
if willPromote:
for pType in ['N', 'B', 'R']:
piece.promote_to(pType)
if not self.white_can_win(turns_left - 1):
piece.undo_promote()
self.undo_move(captured, piece, prev_r, prev_c)
return False
piece.undo_promote()
else:
if not self.white_can_win(turns_left - 1):
self.undo_move(captured, piece, prev_r, prev_c)
return False
self.undo_move(captured, piece, prev_r, prev_c)
return True
if __name__ == '__main__':
games = int(input())
for g in range(games):
board = Board()
cols = "ABCD"
w, b, m = map(int, input().split(" "))
for i in range(w):
ptype, col, row = input().split(" ")
col = cols.index(col)
row = int(row) - 1
board.add_piece("W", ptype, row, col)
for i in range(b):
ptype, col, row = input().split(" ")
col = cols.index(col)
row = int(row) - 1
board.add_piece("B", ptype, row, col)
print("YES" if board.white_can_win(m) else "NO")
View More Similar Problems
Reverse a doubly linked list
This challenge is part of a tutorial track by MyCodeSchool Given the pointer to the head node of a doubly linked list, reverse the order of the nodes in place. That is, change the next and prev pointers of the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list. Note: The head node might be NULL to indicate that the list is empty.
View Solution →Tree: Preorder Traversal
Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's
View Solution →Tree: Postorder Traversal
Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the
View Solution →Tree: Inorder Traversal
In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func
View Solution →Tree: Height of a Binary Tree
The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary
View Solution →Tree : Top View
Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.
View Solution →